[Музички] ЗВУЧНИЦИ 1: Во ред. Сите добредојде назад на секција. Се надевам дека сите вие ​​сте успешно закрепна од вашиот квиз од минатата недела. Знам дека е малку луд во пати. Како што велеше порано, ако сте во рамките на стандардната девијација, навистина не се грижи за тоа, особено за помалку удобно секција. Тоа е за тоа каде треба да биде. Ако не голема, тогаш неверојатна. Kudos за вас. И ако се чувствувам како што треба малку повеќе помош, ве молиме се чувствуваат слободни да се постигне до било која од TFS. Сите ние сме тука да помогнеме. 

Тоа е причината зошто ние ги учат. Тоа е причината зошто јас сум тука секој понеделник за вас момци и во работното време во четврток. Затоа ве молиме да се чувствуваат слободни да дозволете ми да знам Ако сте загрижени за нешто или ако има нешто на квиз дека навистина би сакал да се обрати. 

Така на дневен ред за денес е сите структури на податоци. Некои од овие се само ќе биде само да ви запознаени со овие. Не секогаш може да се спроведе нив во оваа класа. Некои од нив ќе, како за вашиот правопис pset. 

Ќе имате избор меѓу хаш маси и се обидува. Па ние дефинитивно ќе се случува во текот на оние. Тоа се случува да биде дефинитивно повеќе од вид на високо ниво делот денес, иако, бидејќи постојат многу од нив, и ако Влеговме во имплементација детали на сите овие, ние не би дури и да се добие преку поврзани листи а можеби и малку хаш маси. 

Па го носат со мене. Ние нема да се прави колку кодирање тоа време. Ако имате било какви прашања во врска со тоа или сакате да видите го спроведува или ја обидат за себе, Јас дефинитивно препорачувам ќе study.cs50.net, која има примери на сите од нив. Тоа ќе ја имаат мојата PowerPoints со забелешките дека ние имаат тенденција да користат, како и некои програмски вежби, особено за работи како се поврзани листи и бинарни дрва Купишта и знаци. Толку малку повеќе високо ниво, кој може да биде убаво за вас момци. 

Така да со тоа, ние ќе да започнете. И, исто така, yes-- квизови. Мислам дека повеќето од вас кои се во мојот дел да имате квизови, но секој збор или некоја причина не, тие се во право тука во предниот. 

Така поврзани листи. Знам дека ова вид на оди да се врати пред вашиот квиз. Тоа беше пред една недела кои учевме за тоа. Но, во овој случај, ние само ќе одат малку повеќе во длабочина. 

Па зошто би можело да се избере поврзана листа текот низа? Она што го разликува нив? Да? 

ПУБЛИКАТА: Вие може да се прошири на поврзани листа наспроти фиксна големина низа е. ЗВУЧНИЦИ 1: Токму така. Низа има фиксна големина со оглед на тоа поврзана листа има променлива големина. Значи, ако ние не знаеме како колку сакаме за чување, поврзана листа, ни дава големо начин да го направите тоа, бидејќи ние само може да додадете на друг јазол и да додадете на друг јазол и да додадете на друг јазол. Но, она што би можело да биде трампа? Дали некој се сеќавам трампа меѓу низи и поврзани листи? Mmhmm? 

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

ЗВУЧНИЦИ 1: Токму така. Значи со arrays-- 

ПУБЛИКАТА: [нечујни]. 

ЗВУЧНИЦИ 1: Со низи, имаме она што се нарекува случаен пристап. Значи дека ако сакаме она што е некогаш петтата точка од листата или петтата точка на нашата низа, ние само може да го дофати. Ако тоа е поврзана листа, имаме да iterate преку, нели? Така пристапува елемент во низа е константа време, додека со поврзана листа што би најверојатно да биде линеарно време затоа што можеби нашите елемент е целиот пат на крајот. Ние треба да го бара преку сè. Значи со сите овие податоци структури ние ќе да се трошат малку повеќе време на, кои се предности и негативности. Кога би можеле да сакаме да користи еден во однос на другите? И тоа е вид на поголем нешто да земе. 

Значи имаме тука дефиницијата на еден јазол. Тоа е како еден елемент во нашите поврзана листа, нели? Значи сите сме запознаени со нашите typedef structs, што отидовме во текот на преглед последен пат. Тоа беше во основа, само создавање друг вид на податоци што би можеле да ги користат. 

И во овој случај, тоа е некој јазол што ќе се одржи некои цел број во. И тогаш, што е вториот дел тука? Некој? 

ПУБЛИКАТА: [нечујни]. 

ЗВУЧНИЦИ 1: Да. Тоа е покажувач кон следниот јазол. Така што ова, всушност, треба да биде тука. Е покажувач од типот јазол на следната работа. И тоа е она што тие ги опфаќа нашите јазол. Кул. 

Сите во право, па со пребарување, како што беа само велејќи пред рака, ако сте ќе пребарување преку, мора да всушност iterate преку вашиот поврзана листа. Значи, ако ние сме во потрага за бројот 9, ние ќе започне во нашата глава и што ни укажува на почетокот на нашите поврзана листа, нели? И ние се каже, во ред, го прави ова јазол содржи бројот 9? Не? 

Добро, одиме на следниот. Следете го. Дали содржи бројот 9? Број Следете следниот. 

Значи, ние мора да всушност iterate преку нашата поврзана листа. Ние не само може да оди директно до каде е 9. И ако вие момци всушност сакаат да види некои псевдо-кодот до таму. Имаме некои функцијата за пребарување овде што се in-- она ​​што е потребно во? Што мислите? Толку лесна. Што е ова? ПУБЛИКАТА: [нечујни]. ЗВУЧНИЦИ 1: Бројот што го барате. Нели? И што тоа нема да кореспондираат? Тоа е покажувач? 

ПУБЛИКАТА: А јазол. 

ЗВУЧНИЦИ 1: А јазол на листата дека ние сме во потрага на, нели? Па ние имаме некои јазли се покажувачот тука. Ова е момент што се случува да всушност iterate преку нашата листа. Ние се постави тоа еднаков на листата бидејќи тоа е само поставување тоа еднаква на започне од нашите поврзана листа. 

И додека тоа не е NULL, додека ние се уште имаат нешта во нашата листа, провери да се види дали тој јазол има на бројот што го барате. Врати се вистина. Инаку, тоа се ажурира, нели? 

Ако тоа е NULL, ние излезете нашите додека јамка и return false затоа што тоа значи дека ние не го најде. Дали сите да како тоа функционира? ОК. 

Па со вметнување, ќе имаат три различни начини. Можете да Вметни, можете да додадете и може да се вметне во избрани. Во овој случај, ние сме случува да се направи Вметни. Дали некој знае како оние три случаи би можеле да се разликуваат? 

Па Вметни значи дека ќе се стави тоа во предниот дел на вашата листа. Значи тоа би значело дека без разлика она што вашите јазол е, без оглед на што вредноста е, си оди да го стави во право тука пред, во ред? Тоа се случува да биде првиот елемент во вашата листа. 

Ако го додадете, тоа се случува да се оди на грбот на вашата листа. И вметнете во избрани значи дека сте случува да се стави всушност во место каде се држи вашиот поврзана листа подредени. Повторно, како го користите тие и кога ќе го користите нив ќе се разликуваат во зависност од вашиот случај. Ако тоа не треба да се да бидат подредени, Вметни има тенденција да се биде она што повеќето луѓе користат затоа што не мора да одат преку целата листа да се најде на крајот да го додадете на, нели? Вие само може да го држи во право. 

Па ние ќе одиме преку вметнување 1 моментов. Значи едно нешто што јас ќе одам да Силно препорачувам за оваа pset е да се подготви работи надвор, како и секогаш. Тоа е многу важно што ќе се ажурира вашите совети во правилен ред бидејќи ако ги ажурира малку на ред, ви се случува да се заокружи губење на делови од вашата листа. 

Така на пример, во овој случај, ние сме кажува на главата само точка на 1. Ако ние само го направи тоа без зачувување на оваа 1, ние немаме поим што 1 треба да укажуваат на сега затоа што ние сме го изгубиле она што главата посочи. Значи една работа е да се запамети кога правиш Вметни е да се спаси она што главата поени за првиот, тогаш тоа преназначаване, а потоа ажурирање она што вашиот нов јазол треба да укажуваат на. Во овој случај, тоа е еден начин да го направи тоа. 

Значи, ако ние го стореа тоа на овој начин каде што само прераспореден главата, губиме основа на нашата целата листа, нели? Еден начин да го направите тоа е да се има 1 точка да следната, а потоа имаат главата точка 1. Или можете да направите нешто како привремено складирање, кој ми зборуваше за. 

Но прераспределување на вашиот совети во правилен ред се случува да биде многу, многу важно за овој pset. Инаку, ви се случува да имаат хаш маса или се обиде тоа е само ќе биде само дел од зборовите што сакате и потоа you're-- mmhmm? ПУБЛИКАТА: Која беше привремено складирање нешто што се зборува за? ЗВУЧНИЦИ 1: привремено чување. Значи, во основа уште еден начинот на кој би можеле да го направите тоа е чување на чело на нешто, како чувајте го привремената променлива. Додели на 1 и потоа ажурирање 1 до точка на она што главата се користи за да се укаже. На овој начин е очигледно поелегантни затоа што не треба привремена вредност, но само нудат уште еден начин да го направи тоа. И ние всушност имаме некои кодот за ова. Значи за поврзани листа, всушност имаат некои код. Па внесете тука, ова е prepending. Така што ова ќе влезе во главата. 

Па првото нешто, што треба да креирате нов јазол, се разбира, и проверете за NULL. Секогаш добра. А потоа треба да го додели на вредности. Секогаш кога ќе се создаде нов јазол, можете не знам што тоа се покажува кон следната, па сакате да го иницијализирам на нула. Ако тоа не завршуваат покажувајќи на нешто друго, таа добива прераспореден и тоа е во ред. Ако тоа е првото нешто во листата, таа треба да се укаже на нула, бидејќи кој е на крајот на листата. 

Па потоа да внесете го гледаме тука ние се доделува следниот вредноста на нашата јазол да се биде она што главата е, што е она што го имавме тука. Тоа е она што го направија. А потоа ние сме доделување глава до точка на нашиот нов јазол, бидејќи се сеќавам, нова некои покажувач на еден јазол, и тоа е токму она што главата е. Тоа е токму причината зошто ние имаат оваа стрелките accessor. Кул? Mmhmm? 

ПУБЛИКАТА: Дали треба да иницијализира нови до NULL прво, или може да се само да го иницијализирам да се упатат? 

ЗВУЧНИЦИ 1: Нови следната треба да биде NULL да започне затоа што не се знае каде што тоа се случува да биде. Исто така, ова е вид на Исто како парадигма. Ќе го поставите тоа еднаков на NULL само да се направи сигурни дека сите ваши бази се покриени пред да направите било прераспоредување, така што ти си секогаш гарантира дека ќе се укажува на специфична вредност наспроти како ѓубре вредност. Затоа што, да, ние доделите нова следната автоматски, но тоа е повеќе само како добра пракса да се иницијализира на тој начин, а потоа повторно именување. 

Добро, така двојно поврзана листи сега. Што мислите? Она што е различно со двојно поврзана листи? 

Значи, во нашиот поврзани листи, можеме да само се движи во една насока, нели? Ние имаме само следната. Ние само може да оди напред. 

Со двојно поврзана листа, ние, исто така, можат да се движат наназад. Значи имаме не само на број кој сакаме да го чува, имаме каде што укажува на следната и каде што само што дојде од. Па ова им овозможува на некои подобри traversal. 

Значи двојно поврзана јазли, многу слични, нели? Единствената разлика е сега ние имаат следната и претходната. Тоа е единствената разлика. 

Значи, ако ние требаше да Вметни или append-- ние немаат никакви код за ова до here-- но ако сте во ситуација да се обиде и вметнете ја, важно е потребно да се направи сигурни дека сте давање и вашите претходни и вашиот следната покажувачот правилно. Значи во овој случај, што би не само што се иницијализира следната, можете да го иницијализирам претходната. Ако ние сме на чело на листата, ние не само што ќе се направи главата еднаков нови, но нашиот нов претходните треба укажуваат на главата, нели? 

Тоа е единствената разлика. И ако сакате повеќе пракса со овие со поврзани листи, со вметнувањето со бришење, вметнете со во избрани листа, ве молиме проверете study.cs50.net. Има еден куп од голема вежби. Силно ги препорачувам. Би сакал да имавме време да се оди преку нив но има многу на структури на податоци да се добие преку. 

Добро, така хаш маси. Ова е веројатно најголемиот корисна малку за вашата pset тука, бидејќи ви се случува да биде спроведување на еден од овие, или пробајте. Навистина ми се допаѓа хаш маси. Тие се прилично кул. 

Значи, во основа она што се случува е хаш табелата е кога ние навистина треба брзо вметнување, бришење, и збор. Тие се работите кои ние сме приоритети во хаш табелата. Тие може да се добие прилично голем, но како што ќе видиме со неуспешни обиди, постојат нешта кои се многу поголеми. 

Но во основа, сите хаш маса е hash функција кој ви кажува што кофа да се стави секој на вашите податоци, секоја од вашите елементи во. Едноставен начин да се мисли на хаш табелата е дека тоа е само кофи на нештата, нели? Значи, кога сте сортирање работи со како првата буква од нивното име, тоа е вид на како хаш табелата. 

Значи, ако јас се да се групираат вие момци се во групи од кој и да е име започнува со А овде, или кој е роденден е во јануари, февруари, март, без разлика, тоа е ефикасно создавање на хаш табелата. Тоа е само создавање на кофи дека ќе го решите вашиот елементи во така што можете да ги најдете полесно. Па на овој начин кога ми треба да се најде еден од вас, Јас не треба да го бара преку секој од вашите имиња. Јас може да биде како, ох, знам дека Роденден Даниел е in-- ПУБЛИКАТА: --April. ЗВУЧНИЦИ 1: април. Па гледам во мојот април кофата, и со малку среќа, таа ќе биде само еден таму и моето време беше постојано во таа смисла, додека ако јас треба да се погледне преку целиот куп на луѓе, тоа се случува да потрае многу подолго. Па хаш маси се навистина само кофи. Лесен начин да се мисли на нив. 

Така многу важна работа во врска со хаш табелата е хеш функција. Значи она што сум само зборуваше, како вашиот првата буква од вашето име или вашиот роденден месец, овие се идеи кои навистина корелат на хеш функција. Тоа е само начин на донесување на одлука кој можете кофа си елемент оди во, во ред? Значи за оваа pset, можете да барате до доста било хеш функција што го сакате. 

Не мора да биде свој. Има некои навистина кул оние надвор таму кои го прават сите видови на луди математика. И ако сакате да направите вашиот spellchecker супер брз, Јас дефинитивно би се погледне во еден од нив. 

Но, постојат и едноставни, како Пресметај збир на зборови, како и секоја буква има број. Пресмета сумата. Што ја одредува кофа. Тие исто така имаат лесен оние кои се само како и сите на А тука, сите Б е овде. Било еден од нив. 

Во суштина, тоа само ти кажува што низа индекс на вашиот елемент треба да одат во. Едноставно да се одлучат на bucket-- сето тоа е хеш функција е. Значи тука имаме пример кој е само првата буква на стрингот дека сум бил само зборува. 

Па имате некои хаш тоа е само Првата буква од вашето низа минус А, кој ќе ви даде некои број помеѓу 0 и 25. И она што сакате да направите е да бидете сигурни дека ова претставува на големината на вашиот хаш table-- колку кофи постојат. Со многу од овие хаш функции, тие се ќе треба да се враќаат вредности, кои би можеле да биде далеку над бројот на кофи дека вие всушност имаат во вашиот хаш табелата, така што треба да се направи сигурни и современи страна на оние. Инаку, тоа се случува да се каже, ох, тоа треба да биде во кофа 5000 но мора само 30 кофи во вашиот хаш табелата. И, се разбира, сите знаеме дека тоа е ќе резултира со некои луди грешки. Така бидете сигурни дека за современи од страна на големината на хаш табелата. Кул. Така судири. Е секој добар досега? Mmhmm? 

ПУБЛИКАТА: Зошто би го врати таков голем вредност? 

ЗВУЧНИЦИ 1: Во зависност од алгоритам дека вашиот хеш функција користи. Некои од нив ќе направи луди множење. И тоа е за сите добивање на еден дури и дистрибуција, па што го прават некои навистина луди работи понекогаш. Тоа е се. Нешто друго? ОК. 

Така судири. Во суштина, како што реков претходно, во најдобар случај сценарио, било кофа јас се погледне во е ќе има една работа, па јас не треба да се погледне во сите, нели? Јас или знаат дека тоа е таму или тоа е не, и тоа е она што навистина го сакате. Но ако имаме десетици илјади податоци поени и помалку од тоа број кофи, ние ќе треба да имаат судири каде што на крајот нешто се случува да треба да завршат во кофа која веќе има елемент. 

Значи, прашањето е, она што правиме во тој случај? Што ќе правиме? Ние веќе имаме нешто таму? Ние само да го исфрли? 

Број Ние треба да ги задржи двете од нив. Па начинот на кој што ние обично го направите тоа е она што? Што е податочна структура ние само зборуваше за? ПУБЛИКАТА: Поврзано листа. ЗВУЧНИЦИ 1: поврзани листа. Па сега, наместо на секоја од овие кофи само има еден елемент, тоа се случува да содржат поврзана листа на елементите кои беа hashed во неа. Добро, не секој вид на се таа идеја? Затоа што ние не би можеле да имаат низа бидејќи не знаеме колку многу работи се случува да бидат таму. А поврзана листа ни овозможува да се имаат само точниот број кој се hashed во таа кофата, нели? 

Па линеарни љубопитство е во основа тоа idea-- тоа е еден начин да се справи со судир. Што можете да направите е ако, во овој случај, Бери е hashed во 1 и веќе имаме нешто таму, само Продолжувам да одам надолу, додека ќе најдете празен слот. Тоа е еден начин да се справи со неа. На друг начин да се справи со што е со она што ние само called-- поврзани листа се нарекува врзувањето. 

Значи оваа идеја работи, ако вашата хаш табелата мислите е многу поголем од вашите податоци во собата или ако сакате да се обиде и да се минимизира врзувањето додека тоа е апсолутно неопходно. Значи едно е линеарна љубопитство очигледно значи дека вашиот hash функција не е толку корисна бидејќи ви се случува да се заокружи со користење на вашиот хеш функција, да дојдеме до точка, можете линеарни истрагата се сведува на некое место кое е на располагање. Но, сега, се разбира, ништо друго што завршува таму, сте ќе треба да се пребарување и потаму. 

И има многу повеќе трошок за пребарување, кои оди во внесување елемент во вашиот хаш табелата сега, нели? И сега кога ќе одат и да се обидат и да се најде Бери повторно, си оди за да го постигнување, и тоа се случува да се каже, ох, погледнете во кофа 1, и тоа нема да биде во кофа 1, па ти си ќе мора да напречни преку останатиот дел од овие. Така, тоа е понекогаш е корисно, но во повеќето случаи, ние сме случува да се каже дека врзувањето е она што сакате да го направите. 

Значи, ние разговаравме за тоа порано. Добив малку понапред од мене. Но, врзувањето во основа е дека секоја канта во вашиот хаш табелата е само поврзана листа. 

Па на друг начин, или повеќе технички начин, да се мисли на хаш табелата е дека тоа е само низа на поврзани листи, што кога сте пишување вашиот речник и ти се обидуваш да го вчита, размислува за тоа како низа на поврзани листи ќе го направи тоа многу полесно за да се иницијализира. 

ПУБЛИКАТА: Значи хаш табелата има предодредена големина, како [нечујни] кофи? 

ЗВУЧНИЦИ 1: Токму така. Така што има во собата број на кофи дека determine-- што вие момци треба се чувствуваат слободни да си игра со. Тоа може да биде прилично кул да видиме што се случува како што се промени вашиот број на кофи. Но да, тоа има го поставите бројот на кофи. Што ви овозможува да се вклопи како многу елементи како што треба е ова посебна врзувањето каде што се поврзани листи во секоја канта. Тоа значи дека вашиот хаш табелата ќе биде токму големина дека тоа треба да биде, нели? Тоа е целата поента на поврзани листи. Кул. 

Па секој убаво? Сите во право. Ах. Што едноставно се случи? Навистина сега. Претпоставувам дека некој ме убиваат. 

Добро ние ќе одиме во неуспешни обиди, кои се малку луди. Ми се допаѓа хаш маси. Мислам дека тие се навистина кул. Обиди се кул, исто така. 

Па дали некој се сети што се проба е? Треба да се качил над тоа накратко во предавање? Дали се сеќавате вид на како тоа функционира? ПУБЛИКАТА: Јас сум само одобруваат дека ние не одиме над неа. ЗВУЧНИЦИ 1: Ние одиме над неа. Добро, ние сме навистина се случува да се оди над неа сега е она што ние го велиме. 

ПУБЛИКАТА: Тоа е за пронаоѓање дрво. 

ЗВУЧНИЦИ 1: Да. Тоа е пронаоѓање дрво. Страшни. Значи едно нешто да се забележи е дека ние се гледа во индивидуални ликови тука, нели? 

Значи, пред нашите хеш функција, ние се гледа во зборовите како целина, а сега ние сме во потрага повеќе на ликовите, нели? Значи имаме Максвел овде и Мендел. Значи, во основа на try-- начин да се мисли за ова е дека секое ниво тука е низа од букви. Значи ова е вашиот root јазол тука, нели? Ова има сите ликови на писмо за почеток на секој збор. 

И она што сакате да направите е да да речеме, во ред, ние имаме некои М збор. Ние ќе да се погледне за Максвел, па одиме на М. И М поени за цела други низа каде што секој збор, колку што има е збор кој има како второ писмо, се додека постои збор кој има B како втора писмо, тоа ќе има покажувач случува да некои следната низа. 

Има веројатно не збор кој пратеникот нешто, така што во положбата P во овој низа, тоа само ќе биде NULL. Тоа ќе каже, во ред, не постои збор која има М проследено со P, во ред? Значи, ако ние се размислува за тоа, секој еден од овие помали работи е всушност еден од овие големи низи од A до З. Значи она што може да биде една од работите тоа е еден вид на недостаток на проба? 

ПУБЛИКАТА: А многу меморија. 

ЗВУЧНИЦИ 1: Тоа е еден тон на меморија, нели? Секој еден од овие блокови тука претставува 26 простори, 26 елемент низа. Па се обидува да добие неверојатно простор тешки. 

Но, тие се многу брзо. Толку неверојатно брз, но навистина простор неефикасни. Вид на мора да дознаам од кои еден сакате. Овие се навистина кул за вашиот pset, но тие не заземаат многу меморија, така што пласирам. Да? 

ПУБЛИКАТА: Дали тоа ќе биде можно да се постави да се проба и потоа откако ќе ги имаат сите податоци во тоа што можете need-- Јас не знам дали тоа би имало смисла. Бев да се ослободиме од сите NULL ликови, но потоа дека нема да биде во можност да индексира them-- 

ЗВУЧНИЦИ 1: Вие сеуште требаат. 

ПУБЛИКАТА: - на ист начин секој пат. ЗВУЧНИЦИ 1: Да. Ви треба NULL карактери да ги споделите знаете, ако не е зборот таму. Бен имавте нешто што сакате? ОК. Сите права, па ние ќе да одам малку повеќе во техничките детали зад обиде и да работат преку еден пример. 

Добро, така што ова е истото. Додека во поврзана листа, нашата главна вид of-- она ​​што е збор што сакате? - како градење на блок беше еден јазол. Во обид, ние исто така имаме еден јазол, но тоа е дефинирано поинаку. 

Па ние имаме некои bool дека претставува дали еден збор, всушност, постои на оваа локација, а потоа ние имаме некои низа here-- или подобро, ова е покажувач на низа од 27 знаци. И ова е за, во овој случај, тоа 27-- Сигурен сум дека сите од вас се како, чекај, има 26 букви во азбуката. Зошто имаме 27? 

Па во зависност од начинот на кој се спроведе ова, ова е од pset дека дозволено за апостровите. Па затоа екстра еден. Вие исто така ќе имаат во некои случаи на нула терминатор е вклучен како еден од ликови кои тоа е дозволено да биде, и тоа е начинот на кој тие се провери да се види дали тоа е на крајот на зборот. Ако сте заинтересирани, проверете Видео на study.cs50 Кевин, како и Википедија има некои добри ресурси таму. 

Но, ние се случува да се оди преку само вид за тоа како може да се работи преку проба ако ви се доделува еден. Па ние имаме супер едноставен тука има зборови "лилјаците" и "зум" во нив. И како што гледаме тука, овој мал простор тука претставува нашата bool дека вели, да, ова е еден збор. А потоа и оваа има нашата низи од карактери, нели? 

Значи ние се случува да се оди преку наоѓање на "лилјаците" во овој обид. Па почнуваат на врвот, нели? И знаеме дека б одговара вториот индекс, вториот елемент во оваа низа, затоа што a и b. Значи околу вториот. 

И тоа, вели, во ред, кул, следи дека во следниот низа, бидејќи ако ние се сеќавам, тоа не е дека секоја од овие всушност содржи елемент. Секој еден од овие низи содржи покажувач, нели? Тоа е важна разлика да се направи. 

Знам дека ова се случува да be-- обиди се навистина тешко да се добие на прв пат, па дури и ако тоа е втор или трет пат и тоа е уште вид на навидум тешко, Јас ветувам дека ако одите часовник краток повторно утре, тоа најверојатно ќе се направи многу повеќе смисла. Таа ги зема многу да се вари. Јас се уште сум понекогаш како, чекај, што е обид? Како можам да користам ова? 

Значи имаме Б во овој случај, која е нашата втора индекс. Ако имавме, да речеме, C или d или било која друга буква, ние треба да карта дека назад на индексот на нашата низа што што одговара. Значи, ние ќе преземе како rchar а ние само одземе предизвика да го искористи во 0 до 25. Сите добри како ние карта карактери? ОК. 

Значи одиме на втората, а ние види дека, да, тоа не е на нула. Ние може да се движи кон овој следната низа. Па ќе одиме за да овој следната низа тука. 

И ние се каже, во ред, сега ние треба да се види дали е тука. Е нула или го прави тоа всушност се движи напред? Па всушност се движи напред во оваа низа. И ние се каже, во ред, t е нашата последна буква. Значи одиме на т на индекс. А потоа се движиме напред бидејќи има уште еден. А овој вели дека во основа дека, да, таа вели дека постои еден збор here-- дека ако го следат овој пат, сте пристигнале по збор, што го знаеме е "лилјаците". Да? 

ПУБЛИКАТА: Дали е стандард да го имаат тоа како индекс 0, а потоа имаат еден вид на 1 или да имаат на крајот? 

ЗВУЧНИЦИ 1: Не Значи, ако ние се погледне назад на нашите декларација тука, тоа е bool, па тоа е свој елемент во вашата јазол. Па тоа не е дел од низата. Кул. Значи, кога ќе заврши нашиот збор и ние сме во оваа низа, она што сакате да го направите е да направи проверка за е овој збор. И во овој случај, тоа ќе се врати да. 

Така, на тој белешка, ние знаеме дека "зоолошката градина" - ние знаеме како луѓе кои "зоолошката градина" е збор, нели? Но се обидат тука ќе велат, не, тоа не е. И тоа би рекол дека, бидејќи ние не се определени како еден збор тука. Иако ние може да напречни преку оваа низа, овој обид би рекол дека, не, зоолошката градина не е во речникот затоа што ние не треба определени како такви. 

Значи еден начин да се направи that-- ох, жал, оваа. Значи во овој случај ", зоолошката градина" не е еден збор, но тоа е во нашата проба. Но, во овој, велат дека ние го сакаме воведување на зборот "бања", што ќе се случи е ги следиме through-- Б, А, т. Ние сме во оваа низа, и ние одиме за пребарување на час. 

Во овој случај, кога ние се погледне на покажувачот на час, тоа укажува на NULL, во ред? Па освен ако не е експлицитно покажувајќи на друга низа, се претпостави дека сите совети во оваа низа се укажува на нула. Значи во овој случај, ж е да се покажува на нула, па ние не може да направи ништо, така што, исто така, ќе се врати лажни, "бања" не е тука. Па сега ние сме всушност случува да поминат низ како ќе ние всушност се каже дека "зоолошката градина" е во нашиот обид. Како да се вметне "зоолошката градина" во нашата обид? Значи, во истиот начин на кој започнавме со нашите поврзана листа, ние почнуваме во коренот. Кога се двоумите, со почеток во коренот на овие работи. 

И ние ќе каже, во ред, z. z постои во ова, и тоа го прави. Па ти си да се пресели на вашиот следен низа, во ред? И потоа на следниот, ние се каже, во ред, се о постојат? Го прави тоа. Ова повторно. 

И така натаму нашиот следен еден, што рековме, Добро, "зоолошката градина" веќе постои тука. Сите ние треба да направите е да поставите овој еднакви да точно, дека постои еден збор таму. Ако ги следеше сето до пред тој момент, тоа е еден збор, па само поставете ја еднаква на такви. Да? 

ПУБЛИКАТА: Па тогаш, дали тоа значи дека "образование" е збор, исто така? 

ЗВУЧНИЦИ 1: Не Значи во овој случај ", БА" ние ќе ја добие тука, ние би рекол тоа е еден збор, и се уште нема да има. Во ред? Mmhmm? 

ПУБЛИКАТА: Значи откако ќе е тоа збор и ќе се каже да, тогаш тоа ќе содржи да одат на м? 

ЗВУЧНИЦИ 1: Значи ова е да се направи with-- сте вчитување ова. Ќе се каже "зоолошката градина" е збор. Кога ќе отидете на check-- како, да речеме дека сакате да се каже, значи "зоолошката градина" постои во овој речник? Ти си само ќе пребарување за "зоолошката градина" и потоа проверете да се види дали тоа е зборот. Никогаш нема да се движат до м, бидејќи тоа не е она што го барате. 

Значи, ако ние всушност сакаа да додадете "бања" во овој обид, ние ќе го прават истото како што направивме со "зоолошката градина" освен ние ќе видите дека кога ние се обиде да добие до ж, тоа не постои. Па можете да мислам на тоа како се обидува за да додадете нов јазол во поврзана листа, па ние ќе треба да се додаде уште еден еден од овие низи, како така. И тогаш што правиме е ние само го поставите часот елемент на оваа низа укажувајќи на тоа. 

А потоа она што ние би сакале да го правите тука? Додадете еднаква на вистина затоа што тоа е збор. Кул. Знам. Се обидува да не се од највозбудливите. Верувај ми, знам. 

Значи едно нешто да се реализира со неуспешни обиди, Јас реков, тие се многу ефикасни. Па видовме тие заземаат еден тон на просторот. Тие се вид на збунувачки. Па зошто би некогаш ги користат овие? Ние ги користиме овие затоа што тие се неверојатно ефикасен. 

Значи, ако сте некогаш во потрага до збор, вие сте само граничи со должина на зборот. Значи, ако сте во потрага по збор кој е со должина од пет, ти си само некогаш ќе мора да се направи најмногу пет споредби, во ред? Па тоа го прави тоа во основа константа. Како вметнување и пребарување се во основа постојана време. 

Па ако може да ја добие нешто во постојан време, кој е толку добар како што тоа добива. Не можете да добиете подобри од постојана време за овие работи. Па тоа е еден од огромни предности на обидува. 

Но, тоа е многу простор. Па можете вид на мора да одлучи она што е поважно за вас. И на денешната компјутери, простор кој се обиде може да потрае можеби не влијае ви дека многу, но можеби си имаш работа со нешто дека има далеку, далеку повеќе работи, и да се проба само не е разумен. Да? 

ПУБЛИКАТА: Чекај, па имате 26 букви во секој еден? 

ЗВУЧНИЦИ 1: Mmhmm. Да, вие имате 26. Имате некои е зборот маркер, а потоа имате 26 совети на секој еден. И тие се point-- 

ПУБЛИКАТА: И секој 26, тие имаат по 26? 

ЗВУЧНИЦИ 1: Да. И затоа, како што можете да види, таа се шири многу брзо. Сите во право. Значи ние се случува да се влезе во дрвјата, кои Се чувствувам како е полесно и веројатно ќе да биде убаво малку одмор од обиди таму. Па се надевам дека повеќето од вас видовме дрво порано. Не како прилично оние надвор, што јас не знам дали некој отиде на отворено неодамна. Отидов јаболко подигање овој викенд, и ох боже, тоа беше убава. Не знаев лисја може да се погледне што е убаво. 

Така што ова е само дрво, нели? Тоа е само некои јазол, и тоа укажува на еден куп други јазли. Како што гледате тука, ова е вид на периодично тема. Јазли укажува на јазли е вид на суштината на многу структури на податоци. Тоа само зависи од тоа како ние имаат нив укажуваат на едни со други и како можеме да напречни преку нив и како ние вметнете работи кои се определува нивните различни карактеристики. 

Па само некои терминологија, кои јас сум користел досега. Па коренот е се што е во самиот врв. тоа е местото каде што ние секогаш се започне. Можете да мислам на тоа како на главата, исто така. Но, за дрва, тежнееме да се однесуваат на тоа како корен. 

Нешто на дното here-- на многу, многу bottom-- се смета лисја. Па тоа оди заедно со целото дрво работа, нели? Листовите се на рабовите на дрвото. 

А потоа ние, исто така, има неколку смисла да се зборува за јазли во однос еден до друг. Значи ние треба родителот, деца и браќа и сестри. Значи во овој случај, 3 е родител на 5, 6, и 7. Па родител е она што е еден чекор погоре што и да сте се однесуваат на, па само како семејно стебло. Се надеваме, ова е за сите малку малку повеќе интуитивна од обиди. 

Браќа и сестри се сите кои имаат исто родител, нели? Тие се на исто ниво тука. А потоа, како што беше велејќи дека децата се само што е еден чекор подолу јазол во прашање, во ред? Кул. Па бинарен дрво. Секој може да се опасност се погоди на една од на карактеристиките на бинарни дрво? 

ПУБЛИКАТА: Макс две лисја. 

ЗВУЧНИЦИ 1: Токму така. Па максимум од два лисја. Така што во овој еден пред, имавме оваа кој имаше три, но во бинарен дрво, имате максимум од два деца по родител, нели? Има уште една интересна карактеристика. Дали некој знае тоа? Бинарен дрво. 

Па бинарен дрво ќе има сè на the-- ова не е sorted-- но во подредени бинарни дрво, сè на право е поголем од родител, и сè што е на левата страна е помала од родител. И тоа е квиз прашање пред, па добро е да знаете. Па начинот на кој ние се дефинира ова, повторно, имаме уште еден јазол. Ова изгледа многу слично на она што? Двојно 

ПУБЛИКАТА: Поврзано листи 

ЗВУЧНИЦИ 1: Двоен поврзана листа, нели? Значи, ако ние го замени овој со претходниот и следниот, ова ќе биде двојно поврзана листа. Но, во овој случај, ние, всушност, има лево и десно и тоа е тоа. Инаку, тоа е иста. Ние се уште имаат елемент сте во потрага за, а вие само имаат два совети оди на она што е следно. Да, така бинарни пребарување дрво. Ако се забележи, сè на токму тука е поголем than-- или се веднаш овде кон десно е поголем од, сè тука е помалку од. 

Значи, ако ние требаше да пребарувате низ него, треба да изгледа многу блиску до бинарни пребарување тука, нели? Освен наместо на гледање на половина од низа, ние сме само гледајќи во било левата страна или на десната страна од дрвото. Па тоа добива малку поедноставно, мислам. 

Значи, ако вашиот корен е NULL, Очигледно, тоа е само лажна. И, ако е таму, очигледно тоа е вистина. Ако тоа е помалку од, бараме од левата страна. Ако е поголем од, бараме десно. Тоа е точно како бинарни пребарување, само различни податоци структура дека ние сме со користење на. Наместо низа, тоа е само бинарни дрво. 

Добро, Купишта. И, исто така, изгледа ние би можеле да имаат малку време. Ако го правиме, јас сум среќен да се оди повторно над било кој од ова. Добро, така Купишта. Дали некој се сеќавам она што stacks-- било карактеристики на оџакот? 

Добро, па повеќето од нас, мислам, јадат во јадење halls-- колку што ние може да не сакал да. Но, очигледно, може да се мисли на оџак буквално исто како магацинот на коцки или магацинот на нешта. И она што е важно да сфатат е дека тоа е something-- карактеристичните дека ние ја нарекуваме by-- е LIFO. Дали некој знае што дека се залага за? Mmhmm? 

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

ЗВУЧНИЦИ 1: Право, трае во, прв надвор. Значи, ако ние знаеме, ако ние сме редење работи нагоре, најлесната работа за да го дофати off-- а можеби и единственото нешто што може да го дофати исклучи ако нашите магацинот е голем enough-- е дека врвот елемент. Значи она што беше ставен на last-- како што гледаме тука, што беше одложено на повеќето recently-- е ќе биде прв Она што ние убивам, во ред? 

Значи она што го имаме тука е друг typedef struct. Ова е навистина само се допаѓа несреќата се разбира во податочна структура, па има многу фрлени во вас момци. Знам. Значи уште еден struct. Yay за структури. 

И во овој случај, тоа е некој покажувачот на низа што има некои капацитет. Така што ова претставува нашата магацинот тука, како и нашите вистински низа дека во рацете држи нашиот елементи. И тогаш тука имаме некои големина. 

И обично, сакате да го задржите пратите на колку е голема вашиот оџакот е затоа што она што се случува да се овозможи можете да направите е ако знаете големината, тоа ви овозможува да се каже, Добро, сум јас на капацитет? Дали можам да додадам нешто повеќе? И тоа, исто така, ви кажува каде што на врвот на вашиот оџак е па да знаете што ви всушност може да ги тргнеме. И тоа е всушност ќе да биде малку повеќе јасно тука. 

Значи за притисок, една работа, ако некогаш биле за спроведување на притисок, како што беше само велејќи, вашиот магацинот има ограничена големина, нели? Нашите низа имаше некои капацитет. Тоа е низа. Тоа е фиксна големина, па ние треба да бидете сигурни дека ние не сме ставање повеќе во нашата низа од нас всушност имаат простор за. 

Значи, кога сте создавање на притисок функција, прво нешто што направи е да речеме, во ред, имам простор во мојот оџакот? Затоа што ако јас не, жал, Не можам да ги чувате вашите елементи. Ако јас се направи, тогаш ќе сакате да ги чувате ја на врвот на магацинот, нели? 

И ова е причината зошто имаме да ги пратите на нашата големина. Ако ние не ги пратите на нашата големина, не знаеме каде да го стави. Ние не знаеме колку многу работи се во нашата низа веќе. Како очигледно постојат начини дека можеби би можеле да го направи тоа. Вие би можеле да се иницијализира што на нула и потоа проверете за најновите NULL, но многу полесно работа е само да се каже, во ред, да ги пратите на големината. Како знам дека имаат четири елементи во мојата низа, па следното нешто дека ние се стави на, ние сме ќе се сместат на индекс 4. А потоа, се разбира, тоа значи дека сте успешно се наметнува нешто на вашиот оџак, можете сакаат да се зголеми големината така што ќе знаат каде сте, така што ќе може да им помогнам на повеќе нешта. 

Значи, ако ние се обидуваме да pop- нешто надвор од оџакот, она што би можело да биде првото нешто дека сакаме да се провери за? Вие се обидувате да се земе нешто исклучите вашиот оџак. Дали сте сигурни дека има нешто во вашиот оџакот? Број Значи она што може да сакаме да се провери? 

ПУБЛИКАТА: [нечујни]. ЗВУЧНИЦИ 1: Проверете за големината? Големина. Значи, сакаме да се провери да се види дали нашата големина е поголема од 0, во ред? И ако е така, тогаш сакаме да се намали нашата големина од 0 и да се врати тоа. Зошто? 

Во првиот бевме туркање, го наметнува излез големина, а потоа се ажурираат големина. Во овој случај, ние сме decrementing големина а потоа го полетување, кубење тоа од нашата низа. Зошто ние би можеле да го направите тоа? Значи, ако јас имаат едно нешто на мојот стек, она што ќе биде мојата големина во тој момент? 1. 

И каде што е елемент 1 чуваат? На која индекс? ПУБЛИКАТА: 0. ЗВУЧНИЦИ 1: 0. Значи во овој случај, ние секогаш треба да се направи sure-- Наместо враќање Големина на минус 1, бидејќи ние знаеме дека нашите елемент е ќе треба да се чува на 1 помалку без оглед на нашата големина е, ова само се грижи за него. Тоа е малку поелегантни начин. А ние само Намалување на нашите големина и потоа да се вратат големина. Mmhmm? 

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

ЗВУЧНИЦИ 1: Тоа зависи од вашата контекст. Па за некои од теорија, ако си работат with-- ред, дозволете ми да се види дали има благотворно еден што е од корист за повеќе од надвор на CS. Со Купишта, во секое време ви треба да ги пратите на она што е најстариот неодамна додаде е кога сте ќе сакате да го користите оџак. 

И не можам да се сетам на доброто пример за тоа во моментов. Но, кога на најновите нешто што е најважно за вас, тоа е кога оџак се случува да биде корисно. Се обидувам да мислам дека ако таму е добра за ова. Ако мислам дека на добар пример во следните 20 минути, јас дефинитивно ќе ти кажам. 

Но, генерално, дали има нешто, како што реков повеќето, каде најновите е најважно, тоа е каде што магацинот стапува на сцена. Додека редици се вид на спротивното. И сите мали кучиња. Зар не е тоа одлично, нели? Се чувствувам како да сум треба само треба зајаче видео десно во средината на делот за вас момци бидејќи ова е интензивна секција. 

Па редот. Во основа на листа на чекање е како линија. Вие момци јас сум сигурен користење тоа секојдневно, Исто како и во нашата јадење сали. Значи ние треба да се оди во и да се нашите пепелниците, јас сум сигурни дека треба да се чека во ред на удар или да земете вашиот храна. 

Значи разликата тука е дека ова е правилото FIFO. Значи, ако LIFO последен пат беше на прво надвор, FIFO е прв во, прв надвор. Значи ова е местото каде што ќе се стави на првиот е вашиот најважен. Значи, ако сте биле на чекање во line-- може да ви замисли ако отиде во одам да купам новиот iPhone и тоа беше магацинот каде што последниот човек во линија ја доби првата, луѓето ќе го убие едни на други. 

Значи правилото FIFO, сите ние сме многу запознаени со во реалниот свет овде, и сето тоа има врска со всушност вид на Пресоздавањето целата оваа линија и се редат структура. Па додека со стек, имаме притисни и поп. Со ред, ние имаме Стави во ред и dequeue. Па Стави во ред во основа значи стави го на грбот, и dequeue средства ги надвор од напред. Па нашите податоци структура е малку повеќе комплицирано. Имаме Втората работа е да ги пратите. 

Па без глава, ова е токму магацинот, нели? Ова е истата структура како и оџак. Единственото нешто различно денес е што имаат оваа глава, кои што мислите се случува да ги пратите на? 

ПУБЛИКАТА: Првиот. 

ЗВУЧНИЦИ 1: право, Првото нешто што ние се стави во. Шефот на нашата задача. Кој е прв во линија. Сите права, па ако правиме Стави во ред. Повторно, со која било од овие структури на податоци, бидејќи ние сме се занимаваат со низа, ние треба да се провери, ако имаме простор. 

Ова е вид на како ми кажуваше вие момци, ако се отвори датотеката, што треба да се провери за ништовни. Со било кој од овие купчиња и редици, треба да се види дали има простор, бидејќи ние сме кои се занимаваат со фиксна големина низа, како што гледаме here-- 0, 1 сите до 5. Значи она што го правиме во тој случај е проверка за да видат дали ние се уште имаат простор. Е нашата големина помала од капацитет? 

Ако е така, ние треба да се чува на опашката и ние ажурирање нашата големина. Значи она што може да на опашката да биде во овој случај? Тоа не е експлицитно напишано. Како би ја продавницата? Што ќе биде на опашката? 

Па ајде да одиме преку овој пример. Значи ова е низа на големина 6, нели? И ние имаме во моментов, нашата големина е 5. И кога ќе ја ставам, тоа се случува да се оди во петтиот индекс, нели? Па Да се ​​чува на опашката. 

Друг начин да се напише опашка би само биде нашиот спектар на индексот на големината, нели? Ова е големината 5. Следното нешто се случува да одам во 5. Кул? ОК. Станува малку покомплицирано кога ќе почнеме Месинг со главата. Да? 

ПУБЛИКАТА: Дали тоа значи дека ние ќе прогласи низа што беше пет елементи долг и тогаш ние сме додавање на него? 

ЗВУЧНИЦИ 1: Не Значи во овој случај, тоа е оџакот. Ова ќе биде прогласен како низа на големината 6. И во овој случај, ние само треба еден простор лево. 

Добро, па едно е во овој случај, ако нашата глава е на 0, тогаш ние само да го додадете на големина. Но, тоа добива малку сложени да ја формира бидејќи всушност, тие немаат слајд за ова, па ќе одам да се подготви еден, бидејќи тоа не е сосема едноставно штом ќе почне да се ослободиме од нешта. Па додека со оџак можете само некогаш имаат да се грижите за тоа што големината е кога сте додавање на нешто, со задача исто така ќе треба да се направи Осигурајте се дека вашиот шеф е отпаѓаа, бидејќи кул работа во врска со редици е дека ако вие не сте на капацитет, вие всушност може да го заврши околу. 

Добро, така еден thing-- ох, ова е страшно креда. Една работа е да се разгледа е случај. Ние само ќе направи пет. Добро, па ние ќе се велат дека главата е тука. Оваа е 0, 1, 2, 3, 4. 

Шефот е таму, и Ве молиме да имате работи во нив. И ние сакаме да додадете нешто во, нели? Значи она што ние треба да се знам е дека шефот е секогаш случува да се движат на овој начин и тогаш јамка назад наоколу, во ред? 

Значи оваа задача има простор, нели? Таа има простор во самиот почеток, вид на спротивното од ова. Значи она што треба да направите е да се треба да се пресмета на опашката. Ако знаете дека вашиот глава не се пресели, опашка е само вашата низа на индексот на големина. 

Но, во реалноста, ако сте со користење на листа на чекање, вашата глава е веројатно да бидат ажурирани. Значи она што треба да направите е да всушност се пресмета на опашката. Значи она што го правиме е оваа формула тука, за што јас ќе одам да ви ги споделите со момци се размислува за, и тогаш ние ќе зборуваме за тоа. Значи ова е капацитет. 

Така што ова, всушност, ќе ви даде еден начин да го направи тоа. Бидејќи во овој случај, што? Нашата глава е на 1, нашата големина е 4. Ако ние современи дека со 5, добиваме 0, која е местото каде што треба влез него. 

Па тогаш во следниот случај, ако веќе треба да го направите ова, ние се каже, во ред, ајде да dequeue нешто. Ние dequeue ова. Ние извади овој елемент, нели? 

А сега нашата глава е да се покажува тука, и ние сакаме да го додадете во нешто друго. Ова е во основа на назад на нашата линија, нели? Редици може да заврши околу низа. Тоа е една од главните разлики. Купишта, не можете да го направите тоа. 

Со редици, можете да затоа што сите што е важно е кога знаеш што неодамна беше додадена. Бидејќи сè се случува да бидат додадени во оваа лево насока, во овој случај, а потоа заврши околу, можете да продолжи ставање во нови елементи на предниот дел на низа затоа што тоа не е навистина на предниот дел на низа повеќе. Можете да мислам на почетокот на низа како, каде што вашата глава навистина е. 

Значи оваа формула е како ќе се пресмета вашиот опашка. Дали тоа има смисла? ОК. Добро, dequeue, а потоа вие момци имаат 10 минути да ме прашате било кој разјаснување прашања што сакате, затоа што знам дека тоа е лудо. 

Сите права, па во истата way-- Не знам дали вие момци се забележи, но CS е за сите модели. Работите се прилично многу исто, само со ситни измени. Па истото тука. Ние треба да се провери да се види дали ние всушност има нешто во нашата листа на чекање, нели? Се каже, во ред, е нашата големина поголема од 0? Кул. 

Ако го правиме, тогаш се движиме нашата глава, кои е она што јас само покажа тука. Ние ажурирање нашата глава да биде еден повеќе. А потоа ние Намалување на нашите големина и се врати на елемент. 

Има многу повеќе конкретни кодот на study.cs50.net, и Силно препорачувам случува низ него, ако имате време, дури и ако тоа е само една псевдо-кодот. И ако вие момци сакаат да зборуваат преку дека со мене еден на еден, молам дозволете ми да знам. Јас би бил среќен да. Структури на податоци, ако ќе се земе CS 124, ќе знаат дека структури на податоци се многу забава и ова е само почеток. 

Па знам дека е тешко. Тоа е во ред. Ние се бориме. Јас уште не. Па не се грижи премногу за тоа. 

Но, тоа е во основа на вашиот несреќата се разбира во структури на податоци. Знам дека е многу. Има ли нешто што ние би сакале да одат одново? Нешто што сакаме да се зборува преку? Да? 

ПУБЛИКАТА: За таа пример, така новиот опашка е во 0 над тоа? ЗВУЧНИЦИ 1: Да. ПУБЛИКАТА: Добро. Па потоа да оди преку, ќе треба 1 плус 4 or-- 

ЗВУЧНИЦИ 1: Значи сте биле велејќи: кога ние сакаме да одиме направите ова повторно? ПУБЛИКАТА: Да. Значи, ако сте биле пронајдат out-- каде што се можете пресметување на опашката од во тоа? 

ЗВУЧНИЦИ 1: Значи на опашката беше in-- Ја променив ова. Така што во овој пример тука, ова беше низата ние сме во потрага на, во ред? Па ние имаме нешта во 1, 2, 3 и 4. Значи имаме нашата глава е еднаков на 1. оваа точка, и нашата големина е еднакво на 4 во овој момент, нели? 

Вие сите се согласуваат дека е така? Па тоа го правиме на главата плус големина, која ни дава 5, а потоа ние современи 5. Ние се 0, кое ни кажува дека 0 е каде е нашата опашка, каде што имаме простор. 

ПУБЛИКАТА: Што е капа? 

ЗВУЧНИЦИ 1: капацитет. Жал ми е. Така што е големината на вашиот низа. Да? 

ПУБЛИКАТА: [нечујни] пред се враќаме на елемент? 

ЗВУЧНИЦИ 1: Значи ние се движат на главата или да се врати моментот? Значи, ако ние се движат еден, Намалување на големината? Се издржи. Јас дефинитивно заборавив друг. Не е важно. Не постои друга формула. Да, вие би сакале да се вратат на главата, а потоа се движи назад. 

ПУБЛИКАТА: Добро, бидејќи во овој точка, главата беше на 0, а потоа ќе сакаат да се вратат индекс 0, а потоа направи глава 1? 

ЗВУЧНИЦИ 1: Токму така. Мислам дека има уште еден формула нешто како ова. Јас не го имаат на врвот мојата глава како Не сакам да ви даде погрешен. Но, мислам дека тоа е совршено валидни за да речеме, во ред, чувајте овој element-- што елемент на главата е is-- Намалување на вашиот големина, се движи вашата глава над, и враќање она што тој елемент е. Тоа е совршено валидни. ОК. Се чувствувам како тоа не е како most-- не сте ќе одиме од тука како, да, знам дека се обидува. Сето тоа го добив. Тоа е во ред. Јас ветувам. Но, структури на податоци, се нешто што е потребно многу време да се навикнеш на. Веројатно една од најтешките работи, мислам, во текот. 

Така што дефинитивно се повторување и потрага at-- јас навистина не знам поврзани листи се додека не го направи премногу со нив, во истиот начин на кој јас не навистина се разбере совети додека јас сум имал да го предаваат за две години и да го дадам свој psets со неа. Таа ги зема многу на повторување и време. И на крајот, тој вид на ќе кликнете. 

Но, во меѓувреме, ако имате вид на високо ниво разбирање на она што овие се направи, нивните добрите и cons-- што е она што ние навистина имаат тенденција да се нагласи, особено во интро разбира. Како, зошто ние би го користите пробајте над низа? Како, што се позитиви и негативните аспекти на секоја од овие? 

И разбирање на размени меѓу секоја од овие структури е она што е многу поважно во моментов. Може да има еден луд прашање или два, тоа е ќе побара од вас да се спроведе притисок или спроведување поп или Стави во ред и dequeue. Но, во најголем дел, ја презеде дека повисоко ниво разбирање и повеќе на интуитивен разбирање е поважно од, всушност, да биде во можност да се имплементира. 

Тоа би било навистина страшно ако сите од вас би можеле да одат надвор и да си одат се спроведе, се обиде, но ние се разбере тоа не е нужно повеќето разумни нешто во моментов. Но, можете да во вашиот pset, ако сакате да, а потоа ќе добиете пракса, а потоа можеби ќе навистина да го разберат. Да? 

ПУБЛИКАТА: Добро, така што оние се Мислевме да го користите во pset? Дали треба да се користи еден од нив? ЗВУЧНИЦИ 1: Да. Па имате на вашиот избор. Претпоставувам дека во овој случај, може да се зборува за pset малку затоа што трчаше низ овие. Значи во вашиот pset, имате Изборот на обиди или хаш маси. Некои луѓе ќе се обидат и употреба цут филтри, но тие технички не се точни. Поради нивната веројатна природа, тие даваат лажни позитиви понекогаш. Тие се кул изглед во, иако. Силно препорачувам гледајќи во нив барем. Но, вие треба вашиот избор помеѓу хаш табелата и да се проба. И тоа се случува да биде каде што ќе се вчита во вашиот речник. 

И ќе треба да изберете вашиот хеш функција, ќе треба да избере колку Корпи имате, и тоа ќе се разликуваат. Како ако имате повеќе кофи, можеби тоа ќе работи побрзо. Но, можеби сте губи многу простор на тој начин, иако. Што треба да го дознаам. Mmhmm? 

ПУБЛИКАТА: Вие рековте пред тоа може да се користат други хаш функции, дека ние не треба да се создаде хеш функција? 

ЗВУЧНИЦИ 1: Да, во право. Значи буквално за вашиот хеш функција, како Google "хаш функција" и да бараат за некои кул оние. Вие не се очекува да се изгради свој хаш функции. Луѓето го поминуваат своето тези на овие работи. 

Затоа, не се грижите за изградба на свој. Се најде еден на интернет за да се започне со. Некои од нив треба да се манипулира со малку да бидете сигурни дека се врати видови совпаѓаат и какво ли не, па во почетокот, Јас би го препорачал користење на нешто навистина лесно дека можеби само хашови на првата буква. А потоа откако ќе го имаат тоа работа, инкорпорирање на ладилникот хеш функција. Mmhmm? 

ПУБЛИКАТА: А ќе се обиде да биде или ефикасен, но само потешко да, like-- 

ЗВУЧНИЦИ 1: Значи да се проба, мислам, е интуитивно тешко да се имплементира но е многу брзо. Сепак, зазема повеќе простор. Повторно, можете да го оптимизирате и на оние во различни начини и постојат начини to-- ПУБЛИКАТА: Како сме ние оценува на ова? Дали тоа matter-- 

ЗВУЧНИЦИ 1: Па ти си оценето нормален начин. Сте ќе треба да се оценува на дизајн. Кое начин да го направите, вие сакате да бидете сигурни дека тоа е како домот, како тоа може да биде и како ефикасна како тоа може да биде. Но, ако можете да изберете да се проба или хаш маса, се додека тоа функционира, ние сме среќни со тоа. И ако се користи нешто што хашови на првата буква, тоа е во ред, како можеби како дизајн-мудрец. Ние сме, исто така, постигнување на точка во овој semester-- Јас не знам дали сте момци noticed-- ако сте pset оценки опаѓа малку затоа што на дизајнот и какво ли не, тоа е совршено добро. Тоа е да дојдеме до точка каде што вашиот програми се добива се повеќе комплицирани. Постојат повеќе места може да се подобри на. 

Така, тоа е совршено нормално. Тоа не е дека сте го прават полошо на вашиот pset. Тоа е само сме се потешко за вас сега. Па секој е тоа чувство. Јас само оценето сите ваши psets. Знам секој го чувствуваат. 

Затоа, не се загрижени за тоа. И ако имате било какви прашања во врска со пред psets или начини може да се подобри, Се обидувам и коментар на одредени места, но понекогаш тоа е крајот и јас се уморни. Дали има некои други работи за структури на податоци? Сигурен сум дека вие момци навистина не сакаат да зборуваат за нив повеќе, но ако има, јас сум среќен да се одат над нив, како и нешто од предавање минатата недела или минатата недела. 

Знам минатата недела беше ревизија, така ние може да се прескокнат во текот некои преглед од предавање. Било какви други прашања можам да одговорам? Во ред, во ред. Па, вие момци се излезе 15 минути порано. 

Се надевам дека ова беше полу-корисно во најмала рака, и јас ќе се видиме момци следната недела, или четврток работното време. Дали постојат барања за ужина за следната недела, тоа е нешто? Затоа што сум заборавил бонбони денес. И јас го донесов бонбони минатата недела, но тоа беше Колумбо ден, па таму беа како шест лица кои имаше четири торби на бонбони за себе. Јас може да донесе Starbursts повторно ако ви се допаѓа. Starbursts? Добро, тоа звучи добро. Имаат голем ден, момци.