[MUSIC JOC] SPEAKER 1: În regulă. Toată lumea bun venit înapoi la pct. Sper că toate sunt cu succes recuperate de la quiz-ul de săptămâna trecută. Știu că e un pic nebun uneori. Așa cum spuneam mai înainte, dacă ești în abaterea standard, nu vă faceți griji despre asta, mai ales pentru o secțiune mai puțin confortabil. Asta e despre unde ar trebui să fie. Dacă ai făcut mare, atunci minunat. Kudos pentru tine. Și dacă vă simțiți ca ai nevoie un pic mai mult ajutor, vă rugăm să nu ezitați să ajungă la la oricare dintre TFS. Suntem cu toții aici pentru a ajuta. 

De aceea ne-am preda. De asta sunt aici în fiecare luni pentru tine tipi și la birou ore în zilele de joi. Deci, vă rugăm să nu ezitați să să-mi spuneți dacă sunteți îngrijorat de ceva sau dacă e ceva pe testul de pe care doriți într-adevăr să le abordeze. 

Astfel, agenda de astăzi este Totul despre structuri de date. Unele dintre acestea sunt doar de gând să fie doar pentru a vă familiariza cu acestea. Nu aveți dreptul să pună în aplicare vreodată le în această clasă. Unele dintre ele va fi, ca pentru PSET ta abecedar. 

Vei avea alegerea ta între tabele de dispersie și încearcă. Deci, vom fi cu siguranta merge peste ele. O să fi cu siguranta mai mult de natură de o secțiune de nivel înalt astăzi, deși, pentru că există o mulțime de ei, și în cazul în care ne-am dus în detaliile de implementare pe toate acestea, nu ne-ar chiar obține prin liste postat și poate un pic de tabele de dispersie. 

Astfel încât să poarte cu mine. Noi nu vom face la fel de mult codificare acest timp. Dacă aveți orice întrebări despre ea sau vrei să-l vadă pus în aplicare sau încercați să-l pentru tine, Vă recomandăm cu siguranta O să study.cs50.net, care include exemple de toate acestea. Va avea PowerPoints mele cu notele pe care le tind să folosească, precum și unele de programare exerciții, în special pentru lucruri cum ar fi liste legate și binar copaci stive și indicii. Deci, puțin mai înalt nivel, care ar fi frumos pentru voi. 

Deci, cu asta, vom începe. Și, de asemenea, teste yes--. Cred ca majoritatea dintre voi care sunt în pct meu avea teste tale, dar oricine vine în sau dintr-un motiv pe care nu, sunt chiar aici în față. 

Deci, legate de liste. Știu că acest tip de trecut în spate, înainte de testul tău. Asta a fost o săptămână înainte că am aflat despre acest lucru. Dar, în acest caz, vom doar du-te un pic mai mult în profunzime. 

Deci, de ce am putea alege un Lista postat pe un tablou? Ce le deosebește? Da? 

Audiența: puteti extinde o legătură afișat față de dimensiune fixă ​​o serie de. SPEAKER 1: Corect. O matrice a stabilit mărimea întrucât o Lista de legat are o dimensiune variabilă. Deci, dacă nu știm cum mult ne-am dori pentru a stoca, o listă legat ne ofera o mare mod de a face acest lucru pentru că putem pur și simplu adauga un alt nod și se adaugă la un alt nod și se adaugă pe un alt nod. Dar ceea ce ar putea fi un compromis? Are cineva aminte de trade-off între tablouri și liste postat? Mmhmm? 

Audiența: Trebuie sa du-te prin tot drumul prin listă legată găsi un element într-o listă. Într-o matrice, puteți găsi doar un element. 

SPEAKER 1: Corect. Deci, cu arrays-- 

Audiența: [inaudibil]. 

SPEAKER 1: Cu tablouri, avem ceea ce se numește acces aleator. Înseamnă că, dacă vrem ceea ce este vreodată cincilea punct a unei liste sau al cincilea punct de nostru matrice, putem doar să-l apuca. Daca este o listă legată, avem pentru a itera prin, nu? Deci accesarea unui element din o matrice este constanta de timp, întrucât cu o listă legat ea ar fi cel mai probabil sa fie timp liniar, deoarece poate elementul nostru este tot drumul la sfârșitul anului. Trebuie să căutați prin toate. Deci, cu toate aceste date Structurile le vom pentru a petrece un pic mai mult timp pe, Care sunt plusurile si negative. Când s-ar putea vrem să utilizați una peste alta? Și asta e un fel de lucru mai mare pentru a ține departe. 

Deci, avem aici definiție a unui nod. E ca și cum un element în Lista noastră legată, nu? Deci suntem toți familiarizați cu structs noastre typedef, care ne-am dus peste în comentariu ultimul timp. A fost practic doar crearea de un alt tip de date pe care le-ar putea folosi. 

Și în acest caz, e un nod care va organiza unele întreg în. Și atunci ce e de-a doua parte aici? Oricine? 

Audiența: [inaudibil]. 

SPEAKER 1: Da. Este un pointer la nodul următor. Deci, acest lucru ar trebui să fie de fapt aici. Acesta este un pointer de tip nod la următorul lucru. Și asta e ceea ce ei cuprinde nod nostru. Rece. 

În regulă, deci cu căutare, așa cum am fost doar că înainte de mână, dacă ești de gând să caute prin, trebuie sa repeta de fapt prin lista de legat. Deci, dacă ne uităm la numărul 9, ne-ar incepe de la capul nostru și care ne arată la început din lista noastră de legat, nu? Și noi spunem, OK, face acest lucru nod conține numărul 9? Nu? 

Bine, du-te la următorul. Urmareste-l. Nu conține numărul 9? Nu. Urmați următoarea. 

Deci, avem de a repeta de fapt prin lista noastră de legat. Nu putem merge direct la unde 9 este. Și dacă vreți de fapt să a se vedea unii pseudo-cod acolo. Avem o funcție de căutare aici care ia in-- ceea ce nu-l ia în? Ce părere ai? O atât de ușor. Ce este aceasta? Audiența: [inaudibil]. SPEAKER 1: Numărul căutăm. Dreapta? Și ce ar corespunde asta? Este un pointer la? 

Audiența: Un nod. 

SPEAKER 1: Un nod la lista care ne uitam la, dreapta? Deci, avem unele noduri sunt pointer aici. Acesta este un punct care va de fapt repeta prin lista noastră. Ne-am propus aceasta egală cu lista pentru că asta e doar stabilind-o egală cu începe din lista noastră legată. 

Și în timp ce nu e NULL, în timp ce mai avem încă lucruri în lista noastră, verificați pentru a vedea dacă acel nod are numărul căutăm. Întoarcere adevărat. În caz contrar, actualizare, corect? 

Dacă este NULL, ne-am ieși nostru în timp ce buclă și return false pentru că asta înseamnă că nu l-am găsit. Are toată lumea primi cum functioneaza? OK. 

Deci, cu inserție, voi au trei moduri diferite. Aveți posibilitatea să adauge, puteți adăuga și aveți posibilitatea să inserați în asortate. În acest caz, suntem de gând să faci o pune prefix. Stie cineva cum cei trei cazuri s-ar putea diferi? 

Astfel Prefixeaza înseamnă că ai pus se la partea din față a listei. Deci, aceasta ar însemna că, indiferent de ce nodul este, indiferent de ce valoarea este, te duci să-l pună chiar aici în față, OK? O să fie primul element din lista ta. 

Dacă îl adăugați, va pentru a merge la partea din spate a listei. Și introduceți în asortate înseamnă că ești va pune de fapt în locul în cazul în care se păstrează lista de legat sortate. Din nou, modul în care utilizați cei care și atunci când utilizați le va varia în funcție de cazul dumneavoastră. În cazul în care nu are nevoie să fi sortate, Prefixeaza tinde a fi ceea ce majoritatea oamenilor utilizați pentru că tu nu faci trebuie să treacă prin întreaga listă pentru a găsi sfârșitul adauga, nu? Puteți să-l lipi imediat. 

Deci, vom merge printr-o inserție 1 chiar acum. Deci, un lucru pe care am de gând să Recomand cu privire la acest PSET este de a atrage lucrurile, ca întotdeauna. Este foarte important să vă actualizați indicii dvs. în ordinea corectă pentru că dacă le actualizați usor de ordine, vei pune a pierde părți din lista ta. 

Deci, de exemplu, în acest caz, suntem spune capul la doar punctul 1. Dacă ne-am face asta fără a salva acest 1, nu avem nici o idee despre ceea ce 1 ar trebui să indice acum pentru că ne-am pierdut ceea ce capul de subliniat. Deci, un singur lucru să-și amintească când faci un Prefixeaza este de a salva ceea ce puncte de cap de la primul, apoi le retrocedeze, și apoi să actualizeze ce noul nod ar trebui să indice. În acest caz, aceasta este o modalitate de a face acest lucru. 

Deci, dacă am fi făcut-o în acest fel în cazul în care ne-am realocat cap, ne-am pierde practic nostru Întreaga listă, nu? O modalitate de a face acest lucru este de a avea un punct de următor, iar apoi au punctul cap la 1. Sau poti face un fel de depozitarea temporară, pe care am vorbit despre. 

Dar realocarea ta indicii în ordinea corectă va fi foarte, foarte important pentru acest PSET. În caz contrar, vei avea un hash tabel sau o încercare care este doar de gând să fie doar o parte din cuvintele pe care le doresc și apoi Mmhmm ​​you're--? Audiența: Care a fost temporar lucru de stocare vorbeai despre? SPEAKER 1: stocarea temporară. Deci, practic un alt fel ai putea face acest lucru se păstra capul de ceva, cum ar fi depozitați-l variabila temporar. Aloca la 1 și apoi actualizați 1 de la punctul la orice cap de folosit pentru a indica. În acest fel este, evident, mai elegant pentru că nu au nevoie de o valoare temporar, dar oferind doar un alt mod de a face acest lucru. Și noi, de fapt nu au un cod pentru acest lucru. Deci, pentru lista legate, noi de fapt, au un cod. Deci, se introduce aici, acest lucru este precedarea. Deci, aceasta intră în cap. 

Deci, primul lucru, aveți nevoie pentru a a crea noua nod, desigur, și verificați pentru NULL. Intotdeauna bine. Și atunci ai nevoie pentru a atribui valori. Ori de câte ori creați un nou nod, tu Nu știu ce se indică spre viitor, astfel încât pe care doriți să-l inițializa la NULL. În cazul în care se pune indică spre ceva altfel, acesta devine realocată și e bine. În cazul în care e primul lucru în listă, de care are nevoie să indice NULL deoarece că la scos de pe lista. 

Deci, atunci să-l introduceți, vom vedea aici ne sunt atribuirea următoarea valoare a nodului noastre a fi orice cap este, care este ceea ce am avut aici. Asta e ceea ce am făcut. Și apoi ne atribuirea cap la litera la noul nostru nod, pentru că amintiți-vă, noi este un pointer la un nod, și asta este exact ceea ce este șeful. Tocmai de aceea noi au această săgeată accessor. Rece? Mmhmm? 

Audiența: Nu trebuie să ne inițializa nou alături de NULL în primul rând, sau putem doar inițializa la cap? 

SPEAKER 1: New next trebuie să fie NULL pentru a începe pentru că nu știi în cazul în care va fi. De asemenea, acest este un fel de la fel ca o paradigmă. Poti seta o egală cu NULL doar pentru a face -vă că toate bazele sunt acoperite înainte de a face orice schimbare de astfel încât esti mereu garantat că va fie îndreptată către o anumită valoare versus ca o valoare de gunoi. Pentru că, da, am atribui în mod automat nouă următoare, dar e mai mult ca o bune practici pentru a inițializa în acest fel și apoi realocați. 

OK, deci de două ori legate de listele de acum. Ce credem noi? Ce este diferit cu postat de două ori liste? 

Deci, în listele noastre legate, putem muta doar într-o singură direcție, nu? Avem doar urmator. Putem merge doar înainte. 

Cu o listă de două ori legate, De asemenea, ne putem muta înapoi. Deci avem nu numai Numărul de pe care ne-o dorim pentru a stoca, avem în cazul în care se indică următor și unde tocmai am venit de la. Deci, aceasta permite unele traversal mai bine. 

Noduri astfel de două ori legate, foarte asemănătoare, nu? Singura diferență este acum ne au un viitor și o anterior. E singura diferență. 

Deci, dacă ar fi să adauge sau append-- noi nu au nici un cod pentru asta here-- dar dacă ar fi să încercați și introduceți-l, cel mai important lucru este de care aveți nevoie pentru a face -vă că atribuirea atât anterior și dumneavoastră următor pointer corect. Deci, în acest caz, ar trebui să nu numai inițializa următor, ați inițializat anterior. Dacă suntem în fruntea listei, ne-am ar face nu numai cu capul egal nou, dar ar trebui noul nostru precedent punctul de cap, nu? 

Asta e singura diferență. Și dacă vrei mai mult practică cu acestea cu liste postat, cu inserarea, cu ștergerea, cu inserție într-o listă asortate, vă rugăm să verificați study.cs50.net. Există o grămadă de exerciții mari. Am foarte recomanda-le. Aș vrea să avem timp pentru a merge prin intermediul lor dar există o mulțime de structuri de date pentru a obține prin intermediul. 

OK, deci tabele de dispersie. Aceasta este, probabil, cel mai bit util pentru PSET ta aici pentru că ai de gând să fie de punere în aplicare una dintre acestea, sau o încercare. Îmi place foarte mult tabele de dispersie. Sunt destul de rece. 

Deci, practic ceea ce ce se întâmplă este o tabelă de dispersie este atunci când într-adevăr avem nevoie rapid inserare, ștergere, și de căutare. Acestea sunt lucrurile pe care suntem prioritate într-un tabel hash. Ei pot obține destul de mare, dar așa cum vom vedea cu nereușite, sunt lucruri care sunt mult mai mari. 

Dar, practic, toate un hash masă este o funcție hash care vă spune ce găleată pentru a pune fiecare a datelor, fiecare dintre elementele dvs. în. Un mod simplu de a gândi al unui tabel hash este faptul că este doar găleți de lucruri, dreapta? Deci, atunci când sunt sortarea lucruri de la fel ca prima literă a numelui lor, asta e un fel de tabel hash. 

Deci, voi, dacă ar fi să grup este în grupuri de cel care începe numele lui cu un peste de aici, sau oricine e ziua de nastere este în lunile ianuarie, februarie, martie, indiferent, care este efectiv crearea unui tabel hash. E doar crearea de pistoane care să sortați elementele dvs. astfel încât să puteți găsi mai ușor. Deci, în acest fel, atunci când am nevoie pentru a găsi unul dintre voi, Nu trebuie să căutați prin fiecare dintre numele voastre. Pot fi ca, oh, știu că Ziua de nastere Danielle este in-- Audiența: --April. SPEAKER 1: Aprilie. Așa că mă uit în aprilie meu găleată, și cu puțin noroc, ea va fi singura acolo și timpul meu a fost constant în acest sens, întrucât dacă am să uite printr-o grămadă de oameni, o să dureze mult mai mult. Deci, tabele de dispersie sunt într-adevăr doar găleți. Modalitate ușoară de a ne gândim la ei. 

Deci, un lucru foarte important despre un tabel hash este o funcție hash. Deci, lucrurile pe care tocmai am vorbit despre, cum ar fi prima scrisoare de prenumele dvs. sau lună ziua ta de nastere, acestea sunt idei care într-adevăr corelate cu o funcție hash. E doar un mod de a decide care tu cupă element de bază ajungând în, OK? Deci, pentru acest PSET, poti sa te uiti în sus destul de mult orice funcție hash doriți. 

Nu trebuie sa fii propriul tau. Există unele foarte cool afară acolo că face tot felul de matematica nebun. Și dacă doriți pentru a face spellchecker super rapid, Mi-ar siguranta uita-te într-una din cele. 

Dar există, de asemenea, cele simple, cum ar fi de calcul suma cuvinte, cum ar fi fiecare literă are un număr. Calcula suma. Care determină găleată. Ei au, de asemenea, cei care ușor sunt la fel ca toate din aici, toate B e aici. Oricare dintre cele. 

Practic, doar vă spune care index matrice elementul tau ar trebui să meargă în. Doar decide bucket-- totul este o funcție hash este. Deci, aici avem un exemplu care este doar prima literă a șirului care tocmai am vorbit despre. 

Deci, aveți unele hash că e doar prima literă a ta string minus A, care vă va oferi o număr între 0 și 25. Și ce doriți să faceți este să asigurați-vă că aceasta reprezintă dimensiunea hash-ul table-- cât de multe cupe există. Cu multe dintre acestea funcții hash, sunt va fi întoarce valori care s-ar putea fi cu mult mai mare decât numărul de cupe că aveți de fapt în tabel hash, astfel încât aveți nevoie pentru a face sigur și Mod de cei. În caz contrar, se va spune, oh, ar trebui să fie în găleată 5000 dar ai doar 30 pistoane din masa ta de dispersie. Și, desigur, știm cu toții că e va duce la unele erori nebun. Deci, asigurați-vă că Mod de către mărime din masa ta hash. Rece. Astfel de coliziuni. E toată lumea bine până acum? Mmhmm? 

Audiența: De ce ar fi a reveni astfel de o valoare masiv? 

SPEAKER 1: În funcție de algoritmul că funcția hash juca. Unii dintre ei se va face multiplicare nebun. Și este vorba de asistent o distribuție uniformă, astfel încât acestea să fac ceva într-adevăr lucruri nebunești uneori. Asta e tot. Altceva? OK. 

Astfel de coliziuni. Practic, așa cum am spus mai devreme, în cel mai bun caz, orice găleată mă uit în e Va trebui un singur lucru, așa că nu trebuie să se uite la toate, nu? Eu fie Știu că e acolo sau e Nu, și asta e ceea ce ne dorim cu adevarat. Dar dacă avem zeci de mii de puncte de date și mai mică decât cea număr de cupe, vom avea coliziuni în cazul în care în cele din urmă ceva va trebui să se încheie cu un găleată care are deja un element. 

Deci, întrebarea este, ce facem în acest caz? Ce facem? Avem deja ceva acolo? Nu ne-am arunca afară? 

Nu. Noi trebuie să ținem amândoi. Deci, modul în care ne-am de obicei face asta este ceea ce? Care este structura de date ne-am vorbit despre? Audiența: Lista de legat. SPEAKER 1: O listă legat. Așa că acum, în loc de fiecare dintre acestea Cupe cu doar un element, aceasta va conține o listă legată de elementele care au fost distribuit în ea. OK, nu toată lumea un fel de a obține această idee? Pentru că nu am putut avea un tablou pentru că nu știm cât de multe lucruri vor fi acolo. O listă legată ne permite să au doar numărul exact care sunt distribuit în acea găleată, nu? 

Deci, liniar palpare este practic această idee, este un mod de a face cu o coliziune. Ce puteți face este în cazul în care, în acest caz, boabe a fost distribuit în 1 și avem deja ceva acolo, doar menține merge în jos până la veți găsi un slot gol. Asta e un fel să-l ocupe. Un alt mod de a gestiona este cu ceea ce tocmai am called-- legată Lista este numit înlănțuire. 

Deci, această idee funcționează în cazul în care masa ta hash crezi este mult mai mare decât datele stabilite sau dacă doriți să încercați și pentru a minimiza înlănțuirea până când este absolut necesar. Deci, un lucru este liniar palpare înseamnă, evident, că funcția hash nu este la fel de util pentru că ai de gând să ajunge cu ajutorul funcția hash, ajunge la un punct, tu Linear sonda până la un loc care este disponibil. Dar acum, desigur, nimic altceva care se termină acolo sus, ai de gând să trebuie să caută chiar mai jos. 

Și există o mult mai mult cheltuieli de căutare care merge în introducerea unui element din tabelul hash acum, nu? Și acum, când te duci și să încercați și de a găsi bacă din nou, ai de gând să-l hash, și-l va spune, oh, uita-te la găleată 1, și nu va fi în găleată 1, deci ești Va trebui să traverseze prin restul de acestea. Deci, este uneori util, dar în cele mai multe cazuri, vom spune că înlănțuirii este ceea ce vrei sa faci. 

Așa că am vorbit despre acest lucru mai devreme. Am un pic înainte de mine. Dar înlănțuirea este, în principiu faptul că fiecare compartiment în tabel hash este doar o listă legat. 

Deci, un alt mod, sau mai tehnic Astfel, să se gândească la un tabel hash este că este doar o matrice de liste legate, care atunci când scrii în dicționarul ta și încerci să-l încarce, gândire de ea ca o serie de liste postat va face mult mai ușor pentru tine pentru a inițializa. 

Audiența: Deci tabelă de dispersie are o dimensiune predeterminată, ca un [inaudibil] de cupe? 

SPEAKER 1: Corect. Deci, ea are un anumit număr de găleți pe care le determine-- care voi ar trebui nu ezitați să se joace cu. Ea poate fi destul de cool pentru a vedea ce se întâmplă cum ai schimba numărul dvs. de pistoane. Dar da, are un setați numărul de compartimente. Ce vă permite pentru a se potrivi la fel de multe elemente ca ai nevoie este această înlănțuire separat tu unde au legat liste în fiecare compartiment. Asta înseamnă că masa ta de dispersie va fi exact la dimensiune că ai nevoie de ea să fie, nu? Asta e ideea de liste legate. Rece. 

Astfel încât toată lumea în regulă acolo? Bine. Ah. Ce sa întâmplat? Într-adevăr acum. Ghici cineva mă omoară. 

OK vom intra în incearca, care sunt un pic nebun. Îmi place tabele de dispersie. Cred că sunt foarte cool. Încercări sunt cool, prea. 

Deci, nimeni nu amintesc ce o încercați este? Tu ar trebui să fi mers peste l scurt în curs? Îți amintești fel de cum funcționează? Audiența: Eu doar din cap că ne-am dus peste el. SPEAKER 1: Noi mergem peste el. OK, suntem într-adevăr de gând să meargă peste acum este ceea ce spunem. 

Audiența: Asta-i pentru un copac regăsire. 

SPEAKER 1: Da. Este un copac regăsire. Minunat. Deci, un lucru de observat aici este că noi se uita la caractere individuale aici, nu? 

Deci, înainte cu funcția noastră hash, ne-am s-au uitat la cuvintele ca un întreg, iar acum suntem în căutarea mai mult la personajele, nu? Deci avem Maxwell aici și Mendel. Deci, practic un try-- un mod de a gândi despre acest lucru este faptul că fiecare nivel aici este o serie de litere. Deci, aceasta este nodul rădăcină aici, nu? Acest lucru are toate caracterele din alfabet pentru începutul fiecărui cuvânt. 

Și ce doriți să faceți este să să zicem, OK, avem un cuvânt M. Ne vom uita pentru Maxwell, așa vom merge la M. și M puncte la un întreg alte o matrice în care fiecare cuvânt, atâta timp cât există este un cuvânt care are un ca a doua literă, atâta timp cât nu există un cuvânt care are B ca a doua literă, aceasta va avea un pointer merge într-o anumită matrice următor. 

Probabil nu e un cuvânt că MP ceva, astfel încât în ​​poziția P în acest matrice, ar fi doar NULL. S-ar spune, OK, nu există nici un cuvânt care a urmat M de un P, OK? Deci, dacă ne gândim la asta, fiecare unul dintre aceste lucruri mai mici este de fapt una dintre acestea rețele mari de la A prin Z. Deci, ceea ce ar putea fi unul dintre lucrurile care este un fel de rambursare de un try? 

Audiența: O mulțime de memorie. 

SPEAKER 1: Este o tona de memorie, nu? Fiecare dintre aceste blocuri aici reprezinta 26 de spații, 26 element de matrice. Deci, încearcă primi incredibil de spațiu grele. 

Dar ele sunt foarte rapide. Deci, incredibil de rapid, dar într-adevăr spațiu ineficiente. Un fel de trebuie sa dau din care una doriți. Acestea sunt foarte misto pentru PSET ta, dar o fac să ia o mulțime de memorie, astfel încât să compromis. Da? 

Audiența: Ar fi posibil să înființeze un try și apoi Odată ce aveți toate date în ea pe care le need-- Nu știu dacă asta ar avea sens. Am fost a scăpa de toate De caractere NULL, dar apoi tu nu ar fi în măsură să indice them-- 

SPEAKER 1: Încă nevoie de ele. 

Audiența: - la fel de fiecare dată. SPEAKER 1: Da. Ai nevoie de caractere NULL pentru a permite știi dacă nu e un cuvânt acolo. Ben ai avea ceva ce vrei? OK. În regulă, deci vom pentru a merge un pic mai mult în detaliu tehnic din spatele o încerca și de a lucra printr-un exemplu. 

OK, deci acest lucru este același lucru. Întrucât într-o listă legată, principalul nostru un fel de-- ce e cuvântul vreau? - cum ar fi construirea bloc a fost un nod. Într-o încercare, avem, de asemenea, un nod, dar este definită în mod diferit. 

Deci avem ceva bool că reprezintă dacă un cuvânt de fapt există în această locație, și apoi avem unele matrice here-- sau, mai degrabă, acest lucru este un pointer la o matrice de 27 de caractere. Și acest lucru este de, în acest caz, acest 27-- Sunt sigur că toți sunt ca, așteptați, există 26 de litere din alfabet. De ce avem 27? 

Deci, în funcție de fel să pună în aplicare acest lucru, aceasta este de la un PSET care permis de apostrofuri. Deci, de aceea cel suplimentar. Veți avea, de asemenea, în unele cazuri terminator nul este inclusă ca unul dintre cele de caractere care este permis să fie, și că e modul în care acestea verifică la a se vedea dacă Finalul al cuvântului. Dacă sunteți interesat, a verifica afară Video de Kevin pe study.cs50, precum Wikipedia are unele resurse bune de acolo. 

Dar vom trece prin doar un fel de modul în care ar putea lucra printr-o încercare te dacă ești dat unul. Deci, avem un super-simplu aici are cuvintele "Liliacul" si "zoom" în ele. Și, după cum vom vedea aici, acest mic spațiu aici reprezintă bool noastră că spune, da, aceasta este un cuvânt. Iar apoi acest lucru are noastră rețele de caractere, nu? 

Așa că am de gând să treacă prin găsirea "bat" în această încercare. Deci, începe în partea de sus, dreapta? Și știm că b corespunde doilea indice, al doilea element în această matrice, pentru că a și b. Deci aproximativ doua. 

Și se spune, OK, rece, rezultă că în matrice următor, pentru că dacă ne amintim, nu e ca fiecare dintre acestea conține de fapt elementul. Fiecare dintre aceste matrice conține un pointer, nu? Este o distincție importantă de a face. 

Știu că acest lucru se întâmplă pentru be-- încercări sunt într-adevăr greu pentru a ajunge pe prima dată, astfel încât, chiar dacă acest lucru este a doua sau a treia oară și este încă natură de a părea dificil, Promit dacă te duci ceas scurt din nou mâine, se va face, probabil, mult mai mult sens. Este nevoie de o mulțime de digerat. Încă uneori sunt cum ar fi, așteptați, ceea ce este o încercare? Cum folosesc acest lucru? 

Așa că ne-am b, în ​​acest caz, care este al doilea indexul nostru. Dacă am avea, să zicem, C sau d sau orice altă scrisoare, trebuie să ne harta înapoi la index din oferta noastră, care valabil pentru. Așa că ne-ar lua ca rchar și ne-am scade de pe o so hartă în 0 și 25. Toată lumea bine cum ne Harta personajele noastre? OK. 

Deci, mergem la cea de a doua și noi a se vedea că, da, nu este la NULL. Ne putem trece la această matrice următor. Așa că mergem la această matrice următor aici. 

Și noi spunem, OK, acum am nevoie pentru a vedea dacă a este aici. Este nul sau nu-l de fapt, merge mai departe? Deci, un fapt se misca transmite în această matrice. Și noi spunem, OK, t este ultima noastră scrisoare. Deci, vom merge la t la pagina de index. Și apoi vom merge mai departe pentru că există un altul. Și aceasta se spune în esență că, da, se spune că există un cuvânt here-- că, dacă urmați această cale, ați ajuns la un cuvânt, pe care știm că este "bat". Da? 

Audiența: Este standard, pentru a avea acea ca index 0 și apoi au un fel de 1 sau de a avea la sfârșitul anului? 

SPEAKER 1: Nu. Deci, dacă ne uităm înapoi la noastre declarație aici, e un bool, asa ca este elementul său în nodul dumneavoastră. Deci, nu e parte a tabloului. Rece. Așa că atunci când ne-am duce la cuvânt și suntem în această matrice, ceea ce vrem să facem este sa faci o verificare este aceasta un cuvânt. Și în acest caz, s-ar întoarce da. 

Deci, pe această notă, știm că "zoo" - stim ca oamenii care "zoo" este un cuvânt, dreapta? Dar se încerca aici să spun, nu, nu e. Și s-ar spune că pentru că noi nu l-au desemnat ca un cuvânt aici. Chiar dacă putem traversa până la această matrice, aceasta incercare ar spune că, nu, grădină zoologică nu este în dicționar ta pentru că noi nu avem desemnat-o ca atare. 

Deci, un mod de a face that-- oh, îmi pare rău, asta. Deci, în acest caz, "grădină zoologică" nu este un cuvânt, dar este în încercare noastră. Dar în aceasta, spune ne-o dorim introduce cuvântul "baie", ceea ce se întâmplă Este urmăm through-- b, o, t. Suntem în această matrice, și vom merge pentru a căuta h. 

In acest caz, atunci când ne uita-te la indicatorul de la ore, e arătând spre NULL, OK? Deci, dacă nu este în mod explicit arătând spre o altă matrice, voi presupune că toți indicii în această matrice sunt orientate la null. Deci, în acest caz, h este îndreptat la null astfel încât nu putem face nimic, asa ca ar reveni, de asemenea, fals, "baie" nu este aici. Deci, acum suntem de fapt de gând să treacă prin cum ne-ar spune de fapt că "zoo" este în try noastră. Cum putem introduce "zoo", în try nostru? Deci, în același mod în care am început cu Lista noastră legată, vom începe de la rădăcină. Dacă aveți dubii, încep de la rădăcina acestor lucruri. 

Și vom spune, OK, z. z există în acest sens, și-l face. Deci a trece la următoarea matrice, OK? Și apoi pe cea următoare, spunem, OK, nu există o? Ea face. Acest lucru din nou. 

Și așa mai departe unul următoarea noastră, ne-am spus, OK, "grădină zoologică" există deja aici. Tot ce trebuie să faceți este să stabiliți acest egal de adevărat, că există un cuvânt acolo. Dacă ai fi urmat tot până la înainte de acel moment, este un cuvânt, așa că setați-o egală cu astfel de. Da? 

Audiența: Deci nu asta înseamnă că "ba" este un cuvânt de asemenea? 

SPEAKER 1: Nu. Deci, în acest caz, "ba", ne-ar ajunge de aici, ne-ar spune că este un cuvânt, și ar fi tot nu. OK? Mmhmm? 

Audiența: Deci, odată ce este un cuvânt și tu spui da, atunci aceasta va conține pentru a merge la m? 

SPEAKER 1: Deci asta are de a face aplice: sunteți de încărcare acest lucru în. Tu spui "zoo" este un cuvânt. Când te duci la check-- cum ar fi, spune ce vrei să spui, nu "zoo", există în acest dicționar? Esti doar de gând pentru a căuta "zoo", și apoi verificați pentru a vedea dacă e un cuvânt. Niciodată nu o să se mute până la m pentru că nu e ceea ce căutați. 

Deci, dacă am vrut de fapt să add "baie" în această încercare, ne-ar face același lucru așa cum am făcut cu "zoo", cu excepția am vedea că, atunci când ne-am încerca și să obțină la h, aceasta nu există. Deci, vă puteți gândi la acest lucru ca încercarea pentru a adăuga un nou nod într-o listă legată, așa că va trebui să adăugați un alt unul dintre aceste tablouri, cum ar fi așa. Și atunci ce facem este doar ne-am stabilit h element al acestei matrice arătând spre aceasta. 

Și apoi ce am vrea să facem aici? Adaugă-l egal cu adevărat pentru că este un cuvânt. Rece. Știu. Încercări nu sunt cele mai interesante. Crede-mă, știu. 

Deci, un singur lucru pentru a realiza cu nereușite, I-am spus, sunt foarte eficiente. Așa că le-am văzut ei să ia o tona de spațiu. Sunt un fel de confuzie. Deci, de ce ne-ar folosi vreodată astea? Noi folosim aceste, deoarece acestea sunt incredibil de eficient. 

Deci, dacă sunteți vreodată în căutarea un cuvânt, ești doar delimitată de lungimea cuvântului. Deci, dacă sunteți în căutarea pentru o cuvânt care este de lungime cinci, esti doar vreodată va trebui să face din cel mult cinci comparații, OK? Deci, ea face practic o constantă. La fel ca și inserție de căutare sunt, practic, timp constant. 

Deci, dacă puteți obține vreodată ceva în timp constant, asta e la fel de bun ca acesta devine. Nu se poate obține mai bine decât constanta de timp pentru aceste lucruri. Astfel că este unul dintre plusuri imense de încercări. 

Dar aceasta este o mulțime de spațiu. Deci ai un fel de trebuie să decidă ceea ce este mai important pentru tine. Și pe computerele de astăzi, spațiu care un try poate dura până poate că nu afectează tu asta de mult, dar poate ai de a face cu ceva care are mult, mult mai multe lucruri, și o încercare pur și simplu nu este rezonabil. Da? 

Audiența: Stai, astfel încât să aveți 26 litere în fiecare singur? 

SPEAKER 1: Mmhmm. Da, ai 26. Ai ceva este să îi trimită cuvânt și apoi Ai 26 de indicii din fiecare. Și ei point-- 

Audiența: Și fiecare 26, nu fiecare dintre acestea are 26? 

SPEAKER 1: Da. Și de aceea, după cum puteți a se vedea, se extinde destul de rapid. Bine. Deci, vom intra în copaci, care Mă simt ca este mai ușor și, probabil, va fie un răgaz drăguț de încercări acolo. Deci, sperăm, cele mai multe dintre voi au văzut un copac înainte. Nu ca destul de cei din afara, pe care am Nu știu dacă cineva a mers în aer liber recent. M-am dus de mere cules acest week-end, și oh, Doamne, că a fost frumos. Nu știam frunze ar putea arăta că destul de. 

Deci, aceasta este doar un copac, nu? E doar un nod, și-l indică o grămadă de alte noduri. După cum vedeți aici, aceasta este un fel de temă recurentă. Nodurile ce indică spre noduri este un fel de esența multe structuri de date. Este doar depinde de modul în care le-au punctul de reciproc și cum o traversa prin ele și cum o introduce lucruri care determină diferite de caracteristicile lor. 

Deci, doar câteva terminologie, pe care l-am folosit înainte. Deci, radacina este tot ce este la foarte sus. este în cazul în care vom începe mereu. Vă puteți gândi la ea ca și cap de asemenea. Dar pentru copaci, avem tendința de a se referă la ea ca rădăcină. 

Nimic here-- de jos la foarte, foarte bottom-- sunt considerate frunze. Deci, merge împreună cu Toată chestia copac, nu? Frunzele sunt la marginile copac. 

Și apoi avem, de asemenea, o pereche de termeni pentru a vorbi despre noduri în legătură între ele. Deci avem mamă, copii și frați. Deci, în acest caz, 3 este mamă de 5, 6, și 7. Deci, părintele este tot ce este un pas mai sus, indiferent de ce te referindu-se la, asa ca ca un arbore genealogic. Sperăm că acest lucru este tot un pic pic mai intuitiv decat încearcă. 

Fratii sunt orice, care au În același părinte, nu? Sunt la același nivel aici. Și apoi, așa cum am fost spune, copiii sunt doar ceea ce este un pas mai jos nodul în cauză, OK? Rece. Deci, un arbore binar. Poate hazarda cineva o presupunere pe unul dintre caracteristicile arborele binar? 

Audiența: Max două frunze. 

SPEAKER 1: Corect. Deci maxim de două frunze. Deci, în acest o înainte, am avut aceasta care a avut trei, dar într-un arbore binar, Ai un maxim de două copii per părinte, nu? Nu e un alt caracteristică interesantă. Stie cineva asta? Arbore binar. 

Deci, un arbore binar va avea tot pe the-- acesta nu este sorted-- dar într-un arbore binar sortate, tot pe dreapta este mai mare decât părintele, și tot pe stânga este mai mică decât mamă. Și că a fost un test întrebare înainte, atât de bine să știu. Deci, modul în care ne definim acest lucru, din nou, avem un alt nod. Acest lucru arata foarte similar cu ce? De două ori 

Audiența: Linked liste 

SPEAKER 1: O listă dublă legătură, nu? Deci, dacă am înlocui această cu precedent și următor, acest lucru ar fi o listă de două ori legat. Dar, în acest caz, suntem de fapt au la stânga și la dreapta și asta e tot. În caz contrar, e exact la fel. Încă mai avem elementul ce căutați, și trebuie doar doi pointeri merge la orice urmează. Da, arbore de căutare, astfel binar. Dacă observăm, totul pe aici este mai mare than-- sau totul imediat spre dreapta aici este mai mare de, tot aici este mai mică. 

Deci, dacă ar fi să caute prin ea, ar trebui să arate foarte aproape de căutare binare aici, nu? Cu excepția loc de a privi la jumătate matrice, suntem doar cauți fie la stânga lateral sau în partea dreaptă a copacului. Deci, ea devine un pic mai simplu, cred. 

Deci, în cazul în care rădăcină este NULL, în mod evident, este doar fals. Și dacă e acolo, evident că e adevărat. Dacă este mai mică, căutăm stânga. Dacă este mai mare decât, căutăm dreapta. E exact ca și căutare binară, doar o structură de date diferită pe care îl utilizăm. În loc de o matrice, e doar un arbore binar. 

OK, stive. Și, de asemenea, se pare că ar putea avea un pic de timp. Dacă da, eu sunt fericit să merg peste toate astea din nou. OK, așa stive. Are cineva aminte ce stacks-- orice caracteristici ale unui stivă? 

OK, deci cele mai multe dintre noi, cred, mânca în mese halls-- la fel de mult ca noi nu le place să. Dar, evident, vă puteți gândi la o stivă literalmente la fel cum o stivă de tăvi sau un teanc de lucruri. Și ceea ce este important să realizeze este că e something-- caracteristica pe care o numim aceasta by-- este LIFO. Stie cineva ce înseamnă asta? Mmhmm? 

Audiența: trecută intrat, primul ieșit. 

SPEAKER 1: pe dreapta, ultimul intrat, primul ieșit. Deci, dacă știm, dacă suntem stivuire lucruri sus, cel mai ușor lucru pentru a apuca off-- și, poate, singurul lucru pe care îl putem apuca de off dacă stack noastră este enough-- mare este acel element top. Deci, tot ce a fost pus pe last-- așa cum vedem aici, tot ce a fost împins pe cel mai recently-- este Va fi primul lucru pe care noi pop off, OK? 

Deci, ceea ce avem aici este un alt struct typedef. Acest lucru este într-adevăr doar ca o Crash Course în structura de date, deci există o mulțime aruncat la voi. Știu. Deci, încă o struct. Yay pentru structuri. 

Și în acest caz, e un pointer la o serie care are o anumită capacitate. Deci, acest lucru reprezintă stivă nostru aici, ca și oferta noastră reală care a deține elemente noastre. Și apoi aici avem o dimensiune. 

Și de obicei, doriți să le păstrați urmări cât de mare stack-ul tău este pentru că ceea ce se întâmplă, pentru a permite să faci este dacă știți dimensiunea, vă permite să spun, OK, sunt eu la capacitate? Pot să adaug ceva mai mult? Și este, de asemenea, vă spune în cazul în care partea de sus a stack-ul tău este ca să știi ce ai poate lua de fapt oprit. Și că de fapt de gând să fi un pic mai clar aici. 

Deci, pentru împinge, un singur lucru, dacă au fost vreodată la punerea în aplicare a împinge, așa cum spuneam, dumneavoastră stack are o dimensiune limitată, nu? Oferta noastră a avut o anumită capacitate. E un tablou. Este o dimensiune fixă, așa că trebuie să asigurați-vă că nu suntem inscrie mai mult în oferta noastră decât noi de fapt, au spațiu pentru. 

Deci, atunci când creați o apăsare funcția, primul lucru pe care îl faci este să zicem, OK, nu am spatiu in stiva mea? Pentru că dacă nu o fac, îmi pare rău, Nu pot stoca elementul tau. Dacă o fac, atunci doriți să memorați se la partea de sus a stivei, nu? 

Și acesta este motivul pentru care avem pentru a urmări dimensiunea noastră. Dacă nu vom ține cont de dimensiunea noastră, nu știm unde să-l puneți. Nu știm cât de multe lucruri sunt în oferta noastră deja. Ca și în mod evident, există modalități că poate ai putea-o face. Ai putea inițializa totul pentru a NULL și apoi verificați pentru cele mai recente NULL, dar un lucru mult mai ușor pe lângă să spun, OK, ține evidența dimensiune. Ca și cum Știu că am patru elemente în matrice mea, astfel încât următorul lucru că ne-am pus pe, suntem va stoca cel index 4. Și apoi, desigur, acest lucru înseamnă că ați împins cu succes ceva pe stack-ul tău, vă doresc să crească dimensiunea astfel încât să știi unde ești atât de pe care le poate împinge mai multe lucruri pe. 

Deci, dacă noi încercăm să pop ceva de pe stivă, ceea ce ar putea fi primul lucru pe care ne-o dorim pentru a verifica? Pe care încercați să luați ceva de pe stack-ul tău. Ești sigur că există ceva din stack-ul tău? Nu. Deci, ceea ce am putea să doriți să verificați? 

Audiența: [inaudibil]. SPEAKER 1: Verificați pentru dimensiunea? Mărime. Așa că vrem să verificați pentru a vedea dacă dimensiunea noastră este mai mare de 0, OK? Și dacă este, atunci vrem să scadă harta noastră de 0 și să se întoarcă asta. De ce? 

În primul eram împingerea, l-am împins într-o formă mărime și dimensiune, apoi actualizate. În acest caz, vom decrementare dimensiune și apoi luați-l, jumulire aceasta din oferta noastră. De ce am putea face asta? Deci, dacă am un singur lucru pe stivă mea, ceea ce ar fi mărimea mea la acel moment? 1. 

Și în cazul în care este elementul 1 depozitat? La ce indicele? Audiența: 0. SPEAKER 1: 0. Deci, în acest caz, ne vom întotdeauna trebuie să vă sure-- în loc de a se întoarce mărime minus 1, pentru că noi știu că elementul nostru este O să fie păstrat la 1 mai indiferent de dimensiunea noastră este, acest doar are grijă de ea. Este un mod ceva mai elegant. Și ne-am decrementa doar nostru dimensiune și apoi să se întoarcă dimensiune. Mmhmm? 

Audiența: Cred că doar în general, de ce ar fi această structură de date fi benefică? 

SPEAKER 1: Depinde de context ta. Deci, pentru o parte din teorie, dacă lucrați aplice: OK, lasă-mă să văd dacă există un singur benefic care este benefic pentru mai mult de afara de CS. Cu stive, în orice moment aveți nevoie pentru a urmări ceva care este cel mai recent adăugată este atunci când ai de gând să doriți să utilizați o stivă. 

Și nu pot să cred că de o bună exemplu de asta chiar acum. Dar ori de câte ori cele mai recente lucru este cel mai important pentru tine, că, atunci când o stivă va fi util. Încerc să mă gândesc dacă nu e unul bun pentru aceasta. Dacă mă gândesc la un exemplu bun în următorii 20 de minute, vă voi spune cu siguranta. 

Dar, in general, dacă e ceva, cum am spus cel mai mult, în cazul în care cele mai recente este cel mai important, care este în cazul în care un teanc intră în joc. Întrucât cozile sunt un fel de opusul. Și toate micile câinii. Nu e mare, nu? Mă simt ca și cum am ar trebui doar un videoclip iepuras chiar în mijlocul de secțiune pentru voi pentru că aceasta este o secțiune intens. 

Deci, o listă de așteptare. Practic o coadă este ca o linie. Voi Sunt sigur că această utilizare de zi cu zi, la fel ca în sălile de mese. Deci, noi trebuie să mergem în și de a lua tăvi noastre, sunt -vă că trebuie să aștepte în linie pentru înregistrare sau pentru a obține mancarea. 

Deci, diferența aici este că aceasta este FIFO. Deci, dacă LIFO a fost ultimul intrat, primul Out, FIFO este primul intrat, primul ieșit. Deci, acest lucru este în cazul în care orice ai pune pe primul este cel mai important. Deci, dacă ați fost de așteptare într-un line-- puteți imaginați-vă, dacă te-ai dus la du-te noul iPhone și a fost o stivă în cazul în care Ultima persoană în conformitate luat-o în primul rând, oameni ar ucide unii pe alții. 

Așa că FIFO, suntem cu toții foarte familiar cu în lumea reală aici, și totul are de a face cu efectiv un fel de a recrea tot această linie și structura de așteptare. Deci, în timp ce cu stiva, ne-am împinge și pop. Cu o coada, avem Puneți în coadă și dequeue. Deci, Puneți în coadă înseamnă în esență pune-l pe spate, și mijloace dequeue ia off de la partea din față. Deci, structura noastră de date este o pic mai complicat. Avem un al doilea lucru pentru a ține evidența. 

Deci, fără cap, aceasta este exact un stack, nu? Aceasta este aceeași structură ca și o stivă. Singurul lucru diferit acum e că au acest cap, care ce crezi se va urmări? 

Audiența: Prima. 

SPEAKER 1: dreapta, primul lucru pe care am pus în. Șeful coadă noastre. Cine e pe primul loc în linie. Bine, deci dacă facem Puneți în coadă. Din nou, cu oricare dintre aceste structuri de date, deoarece avem de a face cu o serie, avem nevoie pentru a verifica dacă avem spațiu. 

Aceasta este un fel de-mi spui voi, dacă deschideți un fișier, aveți nevoie pentru a verifica nul. Cu oricare dintre aceste stive și cozile, aveți nevoie pentru a vedea dacă există spațiu pentru că suntem de-a face cu o matrice dimensiune fixă, așa cum vom vedea here-- 0, 1 tot de până la 5. Deci, ceea ce facem în acest caz este de verificare pentru a vedea dacă mai avem spațiu. Este dimensiunea noastră mai mică capacitate? 

Dacă este așa, trebuie să-l păstra la coada și ne-am fi actualizat dimensiunea noastră. Deci, ceea ce ar putea fi coada în acest caz? Nu e scris în mod explicit. Cum am păstra? Care ar fi coada? 

Așa că haideți să se plimbe prin acest exemplu. Deci, aceasta este o matrice de dimensiune 6, nu? Și avem acum, dimensiunea noastră este de 5. Și când ne-am pus-o în, va pentru a intra în a cincea index, dreapta? Deci, păstra la coadă. 

Un alt mod de a scrie coadă ar fi doar fi oferta noastră la index de mărime, nu? Aceasta este dimensiunea de 5. Următorul lucru este de gând să meargă în 5. Rece? OK. Ea devine puțin mai complicat când vom începe încurcați cu capul. Da? 

Audiența: Asta înseamnă că noi ar fi declarat o matrice care a fost de cinci elemente de lung și apoi vom adăuga pe ea? 

SPEAKER 1: Nu. Deci, în acest caz, aceasta este o stivă. Acest lucru ar fi declarat ca o serie de dimensiune 6. Și în acest caz, ne vom au doar un singur stângă spațiu. 

OK, deci un lucru este în acest caz, în cazul în care capul nostru este de la 0, atunci ne-am putea adauga la dimensiune. Dar devine un pic mai complicat pentru că, de fapt, ei nu au un diapozitiv pentru aceasta, așa că am de gând să elaboreze o, pentru că nu e destul de simplu, odată ce începe a scăpa de lucruri. Deci, în timp ce cu o stivă doar tu vreodată să vă faceți griji despre ceea ce dimensiunea este atunci când adăugați ceva mai departe, cu o coada, de asemenea, aveți nevoie pentru a face vă că capul este reprezentat, pentru că un lucru misto despre cozile este că, dacă nu ești la capacitate, puteți face de fapt se înfășoare în jurul. 

OK, deci o thing-- oh, acest lucru este creta teribil. Un lucru să ia în considerare este cazul. Vom face doar cinci. OK, deci vom spune capul este aici. Aceasta este 0, 1, 2, 3, 4. 

Capul e acolo, și vă rugăm să aveți lucruri în ele. Și dorim să adăugăm ceva în, nu? Deci, lucru de care avem nevoie pentru a știu este că șeful este întotdeauna de gând să se mute în acest fel și apoi buclă înapoi în jurul, OK? 

Deci, această coadă are spațiu, nu? Ea are spațiu în încă de la început, un fel de opusul acest lucru. Deci, ceea ce trebuie să faceți este să ne nevoie pentru a calcula coada. Dacă știți că dumneavoastră cap nu sa mutat, coada este doar matrice la indicele de mărime. 

Dar, în realitate, dacă utilizați o coadă, capul este, probabil, în curs de actualizare. Deci, ceea ce trebuie să faceți este să calcula de fapt coada. Deci, ceea ce facem noi este această formulă aici, pe care am de gând să te lăsa baieti ne gândim, și atunci vom vorbi despre asta. Deci, aceasta este capacitatea. 

Deci, aceasta va fi de fapt vă oferă o modalitate de a face acest lucru. Pentru că în acest caz, ce? Capul nostru este de la 1, Dimensiune noastră este 4. Dacă ne Mod că de 5, ajungem 0, care este în cazul în care ar trebui să ne input-l. 

Deci, atunci, în cazul următor, dacă ar fi să facem acest lucru, spunem, OK, hai să dequeue ceva. Am dequeue aceasta. Ne scoate acest element, nu? 

Și acum capul nostru este îndreptat aici, și dorim să adăugăm un alt lucru. Aceasta este de fapt din spate a liniei noastre, nu? Cozile se poate încadra în jurul valorii de matrice. Asta e una dintre principalele diferențe. Stive, nu poți face acest lucru. 

Cu cozile, puteți pentru că tot ce contează este ca stii ce S-a adăugat cel mai recent. Din moment ce totul va fi adăugat la această direcție spre stânga, în acest caz, și apoi înfășurați în jurul, puteți continua punerea în elemente noi în partea din față a șirului pentru că nu e adevărat partea frontală a tabloului mai. Vă puteți gândi de la începutul matrice ca în cazul în care capul este de fapt. 

Deci, această formulă este modul în care ai calcula coada ta. Are care face sens? OK. OK, dequeue, iar apoi voi avea 10 minute să-mi pună întrebări clarificarea ce vrei, pentru că știu că e nebun. 

În regulă, deci în aceeași way-- Nu știu dacă voi observa, dar CS este despre toate modelele. Lucrurile sunt destul de mult același, doar cu trucuri mici. Deci, același lucru aici. Avem nevoie pentru a verifica pentru a vedea dacă suntem de fapt au ceva în coadă noastră, nu? Spune, OK, este dimensiunea noastră mai mare decât 0? Rece. 

Dacă da, atunci ne-am muta capul nostru, care este ceea ce am demonstrat aici. Noi actualizăm capul nostru să fie una mai mult. Și apoi ne-am decrementa nostru mărime și să se întoarcă elementul. 

Nu este mult mai concret cod pe study.cs50.net, și am foarte recomanda merg prin ea, dacă aveți timp, chiar dacă e doar un cod pseudo. Și dacă vreți să vorbim prin intermediul că cu mine unu la unu, vă rog să mă lăsați știu. Aș fi fericit să. Structuri de date, în cazul în care luați CS 124, veți stiu ca structuri de date devin foarte distracție și acest lucru este doar începutul. 

Așa că știu că e greu. E în regulă. Noi luptăm. Eu încă o fac. Deci, nu vă faceți griji prea mult despre asta. 

Dar asta este, în principiu ta Crash Course in structuri de date. Știu că e foarte mult. Este ceva pe care noi ar dori să meargă din nou? Orice vrem să vorbim prin intermediul? Da? 

Audiența: În acest exemplu, așa Coada este nou la 0 peste asta? SPEAKER 1: Da. Audiența: OK. Deci, apoi trece prin, ai avea un plus de 4 or-- 

SPEAKER 1: Deci tu spuneai, atunci când vrem să mergem fac asta din nou? Audiența: Da. Deci, dacă ați fost imaginind out-- în cazul în care sunt tu calcularea coada de la asta? 

SPEAKER 1: Deci coada a fost in-- am schimbat acest lucru. Deci, în acest exemplu de aici, aceasta a fost matrice ne uitam la, OK? Deci avem lucruri în 1, 2, 3, 4 și. Deci avem capul nostru este egal cu 1 la acest punct, iar dimensiunea noastră este egal cu 4 în acest moment, nu? 

Sunteți cu toții de acord că e cazul? Deci, vom face capul plus dimensiunea, care ne dă 5, iar apoi am Mod de 5. Primim 0, ceea ce ne spune că 0 este în cazul în care este coada noastră, unde avem spațiu. 

Audiența: Ce este un capac? 

SPEAKER 1: Capacitatea. Scuze. Astfel că este dimensiunea matrice dumneavoastră. Da? 

Audiența: [inaudibil] înainte ne întoarcem elementul? 

SPEAKER 1: Deci, ne-am muta capul sau a reveni în acest moment? Deci, dacă ne mișcăm unul, descrește dimensiunea? Stai. Am uitat cu siguranta un alt. Nu face nimic. Nu există o altă formulă. Da, v-ar dori să se întoarcă cap și apoi mutați-l înapoi. 

Audiența: OK, pentru că în acest punct, capul era la 0, și apoi doriți să reveniți index 0 și apoi face cap 1? 

SPEAKER 1: Corect. Cred că e un alt cu formula un fel de acest lucru. Eu nu-l au pe partea de sus capul meu ca Nu vreau să vă dau o greșit. Dar cred că e perfect valabil la să zicem, OK, păstra acest element-- indiferent element de capul lui este-- decrementa ta dimensiune, mutați capul peste, și retur indiferent de acest element este. Asta e perfect valabil. OK. Mă simt ca și cum acest lucru nu este ca most-- nu ești O să ieși de aici cum ar fi, da, știu încercări. Am tot primit. Asta e OK. Promit. Dar structurile de date sunt ceva care este nevoie de o mulțime de timp să te obișnuiești. Probabil una dintre cele mai grele lucruri, cred că, în cursul. 

Deci, cu siguranta nevoie de repetiție și caută at-- I Nu știu cu adevărat liste postat până când am făcut-o mult prea mult cu ei, în același fel în care nu am făcut- înțeleg cu adevărat indicii până l-am avut să-l predea pentru doi ani și face propriile mele psets cu ea. Este nevoie de o mulțime de repetare și de timp. Și în cele din urmă, se va fel de click. 

Dar, în același timp, dacă aveți un fel de o înțelegere nivel ridicat de ceea ce acestea fac, argumente pro și cons-- care este ceea ce am într-adevăr tendința de a sublinia, în special în cursul intro. Cum ar fi, de ce ne-ar folosi o să încercați pe un tablou? Cum ar fi, care sunt pozitive și negative ale fiecăruia dintre aceste? 

Și înțelegerea compromisuri între fiecare dintre aceste structuri este ceea ce este mult mai important acum. S-ar putea fi unul nebun întrebare sau două care este O să vă rog să pună în aplicare împingere sau punerea în aplicare a pop sau Puneți în coadă și dequeue. Dar pentru cea mai mare parte, cu care înțelegere de nivel superior și mai mult de o înțelegere intuitivă este mai important decât în ​​realitate fiind capabil să-l pună în aplicare. 

Ar fi într-adevăr minunat dacă toți ar putea ieși și du-te să pună în aplicare un eseu, dar am înțeles că nu e neapărat lucrul cel mai rezonabil chiar acum. Dar puteți în PSET ta, dacă vrei a, iar apoi vei primi practică, și atunci poate veți într-adevăr înțeleg. Da? 

Audiența: OK, deci care sunt cele noi menite să folosească în PSET? Nu am nevoie de a utiliza unul dintre ei? SPEAKER 1: Da. Deci, aveți alegerea ta. Cred că în acest caz, putem vorbesc despre PSET un pic pentru că am alergat prin acestea. Deci, în PSET dumneavoastră, aveți dumneavoastră alegerea de încercări sau tabele de dispersie. Unii oameni vor încerca și de a folosi filtre floare, dar cei punct de vedere tehnic nu sunt corecte. Din cauza naturii lor probabilistic, ei da rezultate fals pozitive, uneori. Sunt privire rece în, totuși. Va recomand cu caldura excelentă la ei, cel puțin. Dar există posibilitatea alegerii între o tabelă de dispersie și o încercare. Și care va fi în cazul în care încărcați în dicționarul ta. 

Și veți avea nevoie pentru a alege funcția hash, va trebui să alegeți câte pistoane ai, și aceasta va varia. Ca și în cazul în care aveți mai multe găleți, Poate o să ruleze mai rapid. Dar poate că îți pierzi o mulțime de spațiu în acest fel, deși. Trebuie să-l dau seama. Mmhmm? 

Audiența: Ai spus mai înainte că putem folosi alte funcții hash, că noi nu trebuie să a crea o funcție hash? 

SPEAKER 1: Da, dreapta. Deci, literalmente pentru funcția hash, cum ar fi google "funcție hash" și căutați pentru unele misto. Nu sunt de așteptat pentru a construi propriile funcții hash. Oamenii petrec lor teze cu privire la aceste lucruri. 

Deci, nu vă faceți griji cu privire la construirea propriu. Găsi online, pentru a începe cu. Unele dintre ele trebuie să manipula un pic să se asigure că tipurile de returnare se potrivesc și fleacuri, astfel încât la început, Mi-ar recomanda, folosind ceva într-adevăr ușor că poate doar hash pe prima literă. Și apoi o dată aveți că de lucru, încorporează o funcție hash cooler. Mmhmm? 

Audiența: Ar fi un încerca să fie sau eficient dar doar mai greu de, like-- 

SPEAKER 1: Deci o încercare, cred eu, este intuitiv greu să pună în aplicare dar este foarte rapid. Cu toate acestea, ocupă mai mult spațiu. Din nou, puteți optimiza atât a celor din moduri diferite și există modalități sa-- Audiența: Cât suntem clasificate pe asta? Are matter-- 

SPEAKER 1: Deci gradate mod normal. Vei fi clasificate pe design. Indiferent de modul faci, vrei sa asigurați-vă că este la fel de elegant ca se poate și la fel de eficient ca se poate. Dar dacă alegeți o încercare sau hash masă, atâta timp cât funcționează, suntem fericiti cu asta. Și dacă utilizați ceva care hash pe prima literă, e în regulă, ca poate ca-design înțelept. Suntem, de asemenea, atingerea punct în acest semester-- Nu știu dacă baieti noticed-- daca esti clasele PSET refuza un pic din cauza designului și fleacuri, asta e foarte bine. Se ajunge la un punct în cazul în care dumneavoastră Programele devin mai complicate. Există mai multe locuri vă puteți îmbunătăți pe. 

Deci, este perfect normal. Nu e ca esti face mai rău pe PSET ta. E doar suntem a fi mai greu de pe tine acum. Deci, toată lumea se simte. Am sortat toate psets tale. Știu că toată lumea se simte ea. 

Deci, nu fi îngrijorat de asta. Și dacă aveți întrebări despre psets anterioare sau moduri în care puteți îmbunătăți, Eu încerc să comenteze specificul locuri, dar, uneori, e târziu și eu obosesc. Există și alte lucruri despre structuri de date? Sunt sigur că voi nu prea vreau să mai vorbesc despre ele, dar dacă există, sunt fericit să du-te peste ei, precum și orice de la prelegere acest dribleze săptămână sau săptămâna trecută. 

Știu că săptămâna trecută a fost tot comentariu, așa poate am sarit peste unele recenzie de la curs. Orice alte întrebări pot răspunde? OK, în regulă. Ei bine, voi ieși 15 minute mai devreme. 

Sper că acest lucru a fost semi-ajutor, cel puțin, și Eu vă voi vedea voi săptămâna viitoare, sau orelor de joi. Există cereri de snacks-uri pentru săptămâna viitoare, e chestia? Pentru că am uitat bomboane astăzi. Și am adus bomboane trecut săptămână, dar a fost Columbus Day, deci nu erau ca șase persoane care a avut patru pungi de bomboane pentru ei înșiși. Eu pot aduce starbursts din nou, dacă doriți. Starbursts? OK, sună bine. Ai o zi mare, băieți.