[MUSIC JOC] 

ANDI Peng: Bine ati venit la saptamana 6 de secțiune. Am deviat de la standardul nostru timp de marți secțiune după-amiază la această duminica dimineata minunat. Vă mulțumim pentru toată lumea că mi s-au alăturat astăzi, dar serios, o rundă de aplauze. 

Asta e un efort destul de mare. Eu aproape că nu am chiar face în timp, dar a fost ok. Așa că știu că voi toți tocmai ajuns la testul. Mai întâi de toate, bun venit pentru a de cealalta parte de asta. 

În al doilea rând, vom vorbi despre asta. Vom vorbi despre testul. Vom vorbi despre modul în care faci in clasa. O sa fii bine. Am teste tale pentru te la sfârșitul aici, Deci, dacă vreți să luați o privire la ea, totul bine. 

Atât de repede înainte de a începe, The agenda pentru astăzi este după cum urmează. După cum puteți vedea, suntem ardere practic rapid printr-o grămadă de structuri de date într-adevăr, într-adevăr, foarte repede. Deci, ca atare, acesta nu va fi azi super-interactiv. Va fi doar eu un fel de strigând lucrurile pe care le, și dacă te confunda, dacă am de gând prea repede, lasă-mă să știu. Sunt doar diferite date structuri, precum și în cadrul de PSET pentru acest Săptămâna viitoare, veți va cere să pună în aplicare una dintre ele, probabil, două din them-- două dintre ele în PSET dumneavoastră. OK, așa că doar de gând să începe cu câteva anunțuri. Vom trece peste stive și cozi mai multe în adâncime decât ceea ce am făcut înainte de testul. Vom trece peste legată lista nou, încă o dată, mai în profunzime decât ceea ce am avut înainte de testul. Și apoi vom vorbi despre hash tabele, copaci și încearcă, care sunt destul de necesare pentru PSET ta. Și apoi vom trece peste unele sfaturi utile pentru pset5. 

OK, așa test 0. Media a fost un 58%. A fost foarte scăzută, și așa voi toți a făcut foarte, foarte bine, în conformitate cu ce. 

Destul de mult, regula de degetul mare este daca esti într-un deviație standard a mediei mai ales că suntem într-o mai mică secțiune confortabil, ești în regulă. Ești pe drumul cel bun. Viata e buna. 

Știu că e înfricoșător să cred că Am ca un 40% pe acest test. Am de gând să nu reușească această clasă. Îți promit, nu ești O să reușesc clasa. Ești în regulă. 

Pentru cei dintre voi care au primit peste media, impresionant, impresionant, cum ar fi, serios bine făcut. Le am cu mine. Simțiți-vă liber pentru a veni le obține la sfârșitul secțiunii. Lasă-mă să știu dacă aveți orice probleme, întrebări cu ei. Dacă adăugăm la scorul greșit, să ne anunțați. 

OK, deci pset5, aceasta este într-adevăr o săptămână ciudat pentru Yale, în sensul că PSET noastră se datorează Miercuri la prânz, inclusiv târziu ziua, așa că de fapt din cauza teoretic marți la prânz. Probabil nimeni nu a terminat la marți la prânz. Asta e cu totul în regulă. Vom avea de ore de birou in seara asta la fel de bine ca luni noaptea. Și toate secțiunile săptămâni acest lucru va de fapt, să fie transformat în ateliere de lucru, deci nu ezitați să pop în orice secțiune vrei, și vor fi un fel de mini-PSET ateliere de lucru pentru ajutor pe care. Deci, ca atare, aceasta este singura secțiune în cazul în care ne material didactic. Toate celelalte secțiuni se va concentra exclusiv pe de ajutor pentru PSET. Da? 

Audiența: Unde sunt orelor de program? 

ANDI Peng: ore de birou seara asta oh, bine întrebarea. Cred orelor seara asta sunt în Teal sau la Commons. Dacă tu a verifica on-line CS50 și te duci la ore de birou, ar trebui să existe un program care tu unde toate acestea sunt spune. 

Știu fie in seara asta sau mâine este Teal, și cred că am putea avea Commons pentru noaptea trecută. Nu sunt sigur. Buna intrebare. Verificați pe CS50. 

Rece, orice întrebare privind programul pentru următoarea ca de trei zile? Promit ca voi ca David a spus, aceasta este partea de sus a dealului. Voi sunteți aproape acolo. Doar trei zile. Ajunge acolo, și apoi vom veni toți în jos. Vom avea o pauză CS-free frumos. Bine ai revenit. Vom arunca cu capul în web programare și dezvoltare, lucruri care sunt foarte distractiv, comparativ la unele dintre celelalte psets. Și va fi rece, și vom avea o mulțime de distracție. Vom avea mai multe bomboane. Ne pare rău pentru bomboane. Am uitat bomboane. Era o dimineață dur. Deci voi sunteți aproape acolo, și eu sunt foarte mândru de voi. 

OK, așa stive. Care a iubit la întrebarea despre Jack și hainele de pe testul? Nici unul? OK, e in regula. 

Deci, în esență, după cum puteți Jack, tipul ăsta de aici, îi place să ia hainele din partea de sus a stivei, și el pune din nou pe stiva după ce a făcut. Deci, în acest fel, el nu pare să se la partea de jos a stivă în hainele. Deci, acest tip de descrie structura de date de bază de modul în care este pusă în aplicare o stivă. 

În esență, cred că de o stiva ca orice stivă de obiecte în cazul în care ați pus lucrurile pe partea de sus, și apoi le pop din partea de sus. Deci LIFO este acronimul ne place la use-- Last In, First Out. Și astfel, în ultimul în partea de sus stiva este primul care iese. Și astfel cei doi termeni ne place să se asocieze cu care sunt numite împinge și pop. Când împinge ceva pe produsul stiva, și îl pop înapoi. 

Și așa cred că acest lucru este un fel de concept abstract pentru cei dintre voi care doresc să vadă ca un punerea în aplicare efectivă a acestei în lumea reală. Câți dintre voi au scris un eseu Poate ca o oră înainte de a fi datorat, și ați șters accidental un imens bucată din ea, ca din greșeală? Și apoi ce face de control vom folosi să-l puneți înapoi? Control-Z, da? Control-Z, astfel încât cantitatea de ori că control-Z a salvat viața, a salvat fundul meu, de fiecare dată care este pus în aplicare printr-un coș. 

În esență toate informațiile asta e pe document Word, devine împins și mi-a venit în voie. Și astfel, în esență, ori de câte ori șterge nimic, îl pop înapoi. Și apoi, dacă aveți nevoie de ea din nou, tu împingeți-l, care este ceea ce face de control-C. Și funcția lumea atat de real de structură de date cât de simplu poate ajuta cu viata de zi cu zi. 

Deci, o struct este modul în care vom crea de fapt o stivă. Noi definim tip struct, și apoi noi numim stivă în partea de jos. Și în cadrul stivei, avem doi parametri pe care le putem manipula în esență, așa că avem capacitatea de siruri de caractere char stele. 

Tot ce este de a face este de a crea un tablou pe care le poate stoca tot ce vrei care putem determina capacitatea sa. Capacitatea este doar cantitatea de max articole putem pune în această matrice. int size este contorul care ține urmări cât de multe elemente sunt în prezent în stivă. Deci, atunci putem urmări, A, atât cât de mare stiva reală este, si, B, cât de mult din care stivă am umplut pentru că nu vrem să se reverse asupra a ceea ce capacitatea noastră este. 

Deci, de exemplu, acest minunat Întrebarea a fost pe testul tău. În esență cum putem împinge pe partea de sus a unei stive. Destul de simplu. Dacă te uiți la el, vom trece prin asta. Dacă [Inaudibil] size-- amintiți-vă, ori de câte ori doresc să acceseze orice parametru într-un struct, faci numele struct.parameter. 

In acest caz, s este numele stivă noastre. Vrem pentru a accesa dimensiunea de ea, așa că vom face s.size. Deci, atâta timp cât dimensiunea nu este egală cu capacitatea sau, atâta timp ca este mai mică de capacitate, fie ar lucra aici. 

Vrei pentru a accesa interior din stack, așa s.strings, și ai de gând să pună acest număr nou pe care doriți să introduceți în acolo. Să spunem că va dori să introduceți int n pe stiva, am putea face s.strings, paranteze, s.size egal n. Deoarece dimensiunea este în cazul în care ne-am în prezent se află în stivă dacă vom împinge l pe, ne-am acces oriunde dimensiunea, cu atât plinătatea curent al stivei, și ne-am împinge int n pe ea. Și apoi ne-am dori să vă asigurați că suntem, de asemenea, incrementare dimensiunea n, astfel încât să putem urmări ne-am adăugat un lucru suplimentar pentru stiva. Acum avem o dimensiune mai mare. Are acest sens să aici toată lumea, cum în mod logic funcționează? A fost un fel de rapid. Audiența: Poți trece peste de s.stringss.strings [s.size] din nou? ANDI Peng: Sigur, asa ca ce face s.size prezent ne dea? Audiența: E dimensiunea actuală. ANDI Peng: Exact, așa că Indicele curent că dimensiunea noastră este la, și așa ne-o dorim pentru a pune în noul număr întreg care ne-o dorim pentru a insera în s.size. Are sens? Deoarece s.strings, tot ceea ce este este numele de matrice. Tot ce este este accesarea matrice în struct nostru, și așa, dacă vrem să plasa n în care indicele, putem accesa doar utilizând paranteze s.size. Misto. 

Bine, pop, am pseudocod afară pentru voi, dar concept similar. Are sens? Dacă dimensiunea este mai mare decât zero, atunci Știu că vrei să iei ceva din cauza dacă mărimea nu este mai mare decât zero, atunci nu au nimic în stivă. 

Deci, vrei doar să execute acest cod, se poate doar pop dacă există ceva la pop. Deci, în cazul în care dimensiunea este mai mare decât 0, am minus dimensiunea. Am decrement mărimea și apoi să se întoarcă ceea ce este în interiorul pentru că de popping, dorim să acces indiferent de este stocat în indicele de sus a stivei. Totul face sens? Dacă am făcut voi scrie acest lucru, ar putea să-l scrie voi? OK, voi poate juca în jurul cu ea. Nu vă faceți griji dacă nu înțelegi. Nu avem timp să cod l astăzi pentru că ne-am a primit o mulțime de aceste structuri pentru a merge prin, dar, în esență pseudocod, foarte, foarte asemănătoare pentru a împinge. Doar urmați de-a lungul logica. Asigurați-vă că accesați toate caracteristici ale struct corect. Da? 

Audiența: Va aceste slide-uri și toată chestia asta să fie up-ish azi? ANDI Peng: Întotdeauna, da. Am de gând să încerce să pună asta ca o oră după. Voi trimite un email pentru David, David va încerca să pune-l ca o oră după asta. 

OK, astfel încât atunci vom trece în acest alt structură de date minunat numit-o coadă. Ca voi puteti vedea aici, o coadă, pentru britanici printre noi, tot ce este este o linie. Deci, contrar a ceea ce crezi ca o stivă este, o coadă este exact ceea ce logic credeți că este. Este deținut de regulile FIFO, care este în primul intrat, primul ieșit. Dacă sunteți primul unul în linie, ești prima care iese din linia. 

Deci, ceea ce ne place să numim această este dequeueing și enqueueing. Dacă vrem să adăugați ceva la coada noastră, ne-am Puneți în coadă. Dacă vrem să dequeue, sau de a lua ceva departe, ne-am dequeue. 

Deci același sens în care suntem un fel de crearea de elemente de dimensiuni fixe pe care le poate stoca anumite lucruri, dar putem, de asemenea schimba în cazul în care ne plasarea Parametrii interiorul ei bazat pe ce tip de funcționalitate vrem. Deci stive, am vrut ultimul o, N pentru a fi primul unul. Coada este dorim primul lucru în a fi primul lucru pe. 

Deci de tip struct definesc, după cum puteți vedea, e un pic diferit din ceea ce a fost stivă pentru că nu numai că trebuie să țină urmări în cazul în care dimensiunea este, în prezent, am dori, de asemenea pentru a urmări a capului precum și în cazul în care suntem în prezent sunt. Deci, cred că este mai ușor dacă trag asta. Așa că haideți să ne imaginăm că avem o coadă, Să spunem capul este chiar aici. Șeful de linie, să doar spun că e prezent acolo, și vrem să introduceți ceva în coada de așteptare. Am de gând pentru a apela, în esență, dimensiunea este același lucru ca și coada, la sfârșitul anului oriunde coada este. Să spunem doar că dimensiunea este chiar aici. 

Deci, cum face un practic introduce ceva într-o coadă? Ce index vrem să plasați în cazul în care ne-o dorim pentru a introduce în. Dacă acesta este începutul tău coadă și acesta este sfârșitul anului acesta sau dimensiunea acesteia, în cazul în care facem doriți să adăugați următorul obiect? 

Audiența: [inaudibil] ANDI Peng: Exact, doriți să adăugați l în funcție de ai scris. Fie acest este necompletat sau că este necompletat. Deci vrei să adauga, probabil, aici, pentru că în cazul în care dimensiunea este-- dacă acestea sunt pline, pe care doriți adauga aici, nu? 

Și astfel că, în timp ce foarte, foarte simplu, nu destul de corect întotdeauna pentru că principala diferență între o coada si o stivă este faptul că coada poate de fapt fi manipulat astfel încât modificările cap în funcție de locul în care doriți începutul tac dumneavoastră pentru a începe. Și, ca rezultat, coada este, de asemenea, va schimba. Și astfel încât să ia o privire la acest cod acum. Ca voi, de asemenea, au fost rugati sa scrie pe testul, Puneți în coadă. Poate vom vorbi prin ce răspunsul a fost ceea ce a fost. 

Nu am putut potrivi destul de această linie pe una, dar, în esență această bucată de cod ar trebui să fie pe o linie. Petreceți ca 30 de secunde. Aruncati o privire, și a vedea de ce acesta este modul în care aceasta este. 

Foarte, foarte asemănătoare struct, foarte, foarte structură similară ca în cazul precedent stiva cu excepția, poate, pentru o linie de cod. Și că o linie de cod determină funcționalitatea. Și-l diferențiază într-adevăr o coadă dintr-o stivă. 

Oricine vrea să ia o lovitură de cuțit la explica de ce ai luat acest lucru complicat aici? Vedem revenirea nostru minunat prieten modul. Ca voi va veni în curând să recunoască în programare, aproape oricand ai nevoie de ceva să-și încheie în jurul valorii de nimic, modul va fi modul de a face acest lucru. Deci, știind că, nimeni nu vrea pentru a încerca să explice că linie de cod? Da, toate răspunsurile sunt acceptat și bun venit. Audiența: Vorbești cu mine? ANDI Peng: Da. Audiența: Oh, nu îmi pare rău. ANDI Peng: OK, așa că hai să plimbare prin acest cod. Deci, atunci când sunteți încercarea de a adăugați ceva pe-o coadă, în cazul în care se întâmplă minunat cap să fie aici, e foarte ușor pentru noi pentru a merge doar până la capăt introduce ceva, nu? Dar ideea de o coadă este că șeful de fapt, poate dinamic modifica în funcție de cazul în care ne-am doresc începerea Q nostru de a fi, și, ca atare, coada este, de asemenea, va schimba. 

Și așa ne imaginăm că nu acesta este fost coadă, ci mai degrabă aceasta a fost coada. Să spunem că capul este chiar aici. Să spunem coadă nostru arata ca aceasta. Dacă ne-am dorit pentru a schimba în cazul în care începutul liniei este, să spunem că ne-am mutat capul în acest fel și dimensiuni de aici. 

Acum dorim să adăugăm ceva la această coadă, dar voi poate vedea, nu este atât de simplu ca doar la adauga tot ceea ce este după mărimea pentru că atunci ne-am alerga afară de limite de oferta noastră reală. În cazul în care dorim să adăugați într-adevăr este aici. Asta e frumusetea de o coadă este că pentru noi, vizual se arata ca linia merge ca aceasta, dar atunci când este păstrat într-o structură de date, ei da ca ca un ciclu. Un fel de se încadrează în jurul în față la fel că o linie poate, de asemenea încheia în jurul valorii de în funcție de oriunde te-ai doresc să începutul liniei de a fi. Și așa, dacă vom lua o uite aici, să spune am vrut să creeze un functie numita Puneți în coadă. Ne-am dorit pentru a adăuga int n în care q. Dacă q.size q-- vom suna ca datele noastre structure-- dacă queue.size nostru nu egală cu capacitatea sau dacă este mai puțin decât capacitatea, q.strings este matrice în q nostru. Vom stabili care egal cu q.heads, care este chiar aici, plus q.size Modulul de capacitatea, care înfășurați-ne înapoi pe aici. 

Deci, în acest exemplu, indicele de cap este de 1, nu? Indicele de mărime este 0, 1, 2, 3, 4. Deci, putem face un plus 4 modul prin capacitatea noastră, care este de 5. Ce ne dea? Care este indicele care iese din asta? 

Audiența: 0. 

ANDI Peng: 0, care se întâmplă să fie chiar aici, și așa ne-o dorim să fie în măsură pentru a introduce în chiar aici. Și astfel această ecuație aici gen de doar funcționează cu orice numere în funcție de locul dvs. cap și dimensiunea sunt. Dacă știi ce cei lucrurile sunt, știi exact unde doriți să inserați tot ce este dupa coada ta. Asta face sens pentru toată lumea? 

Știu un fel de creier teaser mai ales că acest a venit în urma test dumneavoastră. Dar sperăm că toată lumea acum se poate înțelege de ce această soluție sau acest funcție este modul în care aceasta este. Oricine un pic neclar cu privire la acest? BINE. 

Și așa acum, dacă a vrut să dequeue, acest este în cazul în care capul nostru ar fi trecerea pentru că dacă ar fi să dequeue, nu ne scoate la sfârșitul q. Vrem să-și scoată capul, nu? Deci, ca urmare, cap se va schimba, și de aceea, atunci când Puneți în coadă, le-ați luat pentru a urmări în cazul în care capul și dimensiunea trebuie să fie capabilă să insereze în poziția corectă. 

Și așa, atunci când dequeue, Am, de asemenea, o pseudocod afară. Simțiți-vă liber să, dacă doriți să încerce codificare asta. Doriți să mutați capul, nu? Dacă aș vrea să dequeue, am s-ar muta capul peste. Acest lucru ar fi capul. 

Și dimensiunea noastră actuală ar scade pentru că noi nu mai au patru elemente din matrice. Avem doar trei, iar apoi ne-o dorim pentru a reveni orice a fost depozitat în interiorul a capului pentru că vrem să profit de această Valoarea așa de foarte similar cu stiva. Doar tu iei dintr-un loc diferit, și va trebui să realocați indicatorul la alt loc ca un rezultat. În mod logic, toată lumea să urmeze? Grozav. 

OK, deci vom vorbi un pic mai în profunzime despre listele legate pentru că ei vor fi foarte, foarte valoros pentru tine în cursul acestei saptamani psets. Liste legate, ca voi pot aminti, toate acestea sunt sunt noduri care sunt nodurile de anumite Valorile atât o valoare și un pointer care sunt legate împreună de aceste indicii. Și astfel struct cu privire la modul vom crea un nod aici e că au int n, care este indiferent valoarea într-un magazin sau un șir n sau ce vrei să numesc, n stele char. Struct stele nod, care este indicatorul pe care doriți să aveți în fiecare nod, ai de gând să aibă ca Punct de pointer spre viitor. Vei avea capul de o listă care este legat a merge la punctul de restul valorile așa mai departe și așa mai departe până când ajungeți în cele din urmă la sfârșitul. Și acest ultim nod este doar va să nu aibă un pointer. Se va indica nul, și atunci știi că ai lovit sfârșitul listei de legat este atunci când ultima dvs. pointer nu indică nimic. 

Deci vom merge un pic mai mult în profunzime cu privire la modul în care s-ar putea, eventual, Căutare o listă legată. Amintiți-vă ce sunt unele dintre dezavantaje ale listelor legate versetele o serie cu privire la căutări. O serie puteți căuta binar, dar de ce nu se poate face asta într-o listă legată? 

Audiența: Pentru că sunt toate conectate, dar nu știu de unde destul de [Neauzit]. 

ANDI Peng: Da, exact așa amintesc că strălucirea de o serie a fost faptul că am avut memorie cu acces aleator în cazul în care dacă am vrut valoarea din indexul șase, am putea spune doar index șase, da-mi ca valoarea. Și asta pentru că matrice sunt sortate într-un spațiu contiguu de memorie într-un singur loc, în timp ce fel de liste legate sunt intercalate aleator în jurul, și singura modalitate de puteți găsi unul este printr-un pointer care vă spune adresa de unde care nod următor este. 

Și astfel, ca urmare, singura cale pentru a căuta într-o listă legată este căutarea liniară. Pentru că nu știu exact unde valoarea 12 în lista legat este, Trebuie să traverseze în întregime de care lista pe o legătură câte unul de la cap la primul nod, la al doilea nod, la a treia nodul, tot drumul în jos, până când în cele din urmă mă unde acel nod caut este. Și astfel, în acest sens, căutare pe o listă legată este întotdeauna n. Este întotdeauna n. E mereu la timp liniar. 

Și astfel codul în care punem în aplicare acest lucru, iar acest lucru este un pic nou pentru voi de când ați baieti nu au într-adevăr vorbit despre sau vreodată indicii văzut în modul de căutare prin indicii, asa ca vom trece prin acest lucru foarte, foarte încet. Deci căutare bool, dreapta, să ne imaginăm vrem pentru a crea o funcție numită căutare care returnează true dacă ați găsit o valoare în interiorul strâns legat listă și returnează false altfel. Lista de stele nod este în prezent doar indicatorul la primul element din lista de legat. int n este valoarea pe care ești căutarea în această listă. 

Deci, pointer stele nod este egal listă. Asta înseamnă că suntem de stabilire și crearea unui pointer în acest primul nod din interiorul listei. Toată lumea cu mine? Deci, dacă ar fi să mergem aici, mi-ar fi initializat un pointer care indică spre indiferent capului că lista este. 

Și apoi odată ce te aici, în timp ce indicatorul nu egal nul, astfel încât este bucla în care suntem O să fie ulterior traversează restul lista noastră pentru că ceea ce se întâmplă atunci când indicatorul este egal nul? Noi știm că have-- 

Audiența: [inaudibil] 

ANDI Peng: Exact, așa știm că am ajuns la sfârșitul listei, nu? Dacă te duci înapoi aici, fiecare nod Trebuie arătând spre un alt nod și așa mai departe și așa mai departe până în cele din urmă te-a lovit coada de lista legate, care are un pointer care tocmai nu indică nicăieri, altele decât nr. Și ca să știți că, practic lista este încă acolo sus până pointer nu este egal nul deoarece odată ce este egal nul, știi că nu există mai multe lucruri. 

Deci, care este bucla în care suntem Va trebui de căutare actuale. Și dacă pointer-- vedeți acest tip de funcții săgeată acolo? Deci, dacă indicatorul de n, în cazul în care indicatorul la n egal egal n, astfel că înseamnă că, dacă indicatorul ca esti căutarea pe la sfârșitul fiecărui nod este de fapt egală cu valoarea sunteți în căutarea pentru, apoi doriți să reveniți adevărat. Deci, practic, dacă ești la un nod care are valoarea pe care o căutați, știi că ai fost posibilitatea de a căuta cu succes. 

În caz contrar, pe care doriți să setați pointer la nodul următor. Asta este ceea ce linia de aici este de a face. Pointer este egal cu indicatorul următor. Toată lumea vedea cum că lucrează? 

Și, în esență, ai de gând să doar traversa totalitatea listei, resetarea indicatorul de fiecare dată, până când vă în cele din urmă a lovit la sfârșitul listei. Și știi că nu există mai multe noduri pentru a căuta prin, și apoi vă puteți întoarce false pentru că știți că, oh, bine, dacă am fost în stare pentru a căuta prin totalitatea listei. Dacă în acest exemplu, dacă am vrut să caute pentru valoarea de 10, și am început la cap, și Caut tot drumul în jos, și, eventual, am ajuns la acest lucru, care un pointer care indică spre nul, Știu asta, rahat, cred 10 nu este în această listă pentru că nu am putut găsi. Și eu sunt la sfârșitul listei. Și în cazul în care știți Am de gând să se întoarcă false. 

Lăsa să se scufunda într-un pic. Acest lucru va fi destul de important pentru PSET ta. Logica este foarte simplu, poate sintactic doar de punere în aplicare. Vreți să facă vă că ați înțeles. Misto. 

OK, deci cum ne-ar fi inserarea de noduri, drept, într-o listă amintesc că Care sunt ceea ce a beneficiilor de a avea o listă legată față de o serie în termeni de stocare? 

Audiența: E dinamic, așa că este mai ușor sa-- 

ANDI Peng: Exact, așa că este dinamic, care înseamnă că se poate extinde și micșora în funcție de nevoile utilizatorului. Și astfel, în acest sens, nu avem nevoie de a deșeurilor de memorie inutile pentru că am dacă nu știu cât de multe valori Vreau la magazin, aceasta nu are sens pentru mine pentru a crea un tablou pentru că dacă vreau să stocați 10 valori și pot crea o serie de 1.000, care este o mulțime de memorie pierdut, alocat. De aceea, dorim să utilizați o legătură Lista pentru a putea dinamic schimba sau micșora dimensiunea noastră. 

Și pentru ca face inserție un pic mai complicat. Din moment ce nu pot accesa la întâmplare elemente modul în care ne-ar de o matrice. Dacă vreau să insera un element în a șaptea index, Eu doar pot insera în a șaptea index. Pe o listă legată, aceasta nu destul de lucru la fel de ușor, și așa, dacă ne-am dorit pentru a introduce cel aici, în lista legate, vizual, este foarte ușor pentru a vedea. Vrem doar să-l introduceți acolo, chiar de la începutul listei, imediat după cap. 

Dar modul în care trebuie să realocați indicii este un pic complicate sau, în mod logic, este logic, dar doriți să vă asigurați că-l ai complet în jos pentru că ultimul lucru pe care doriți este de a realoca un pointer astfel încât facem aici. Dacă ați dereference pointer la cap la 1, apoi dintr-o brusc restul lista legate este pierdut pentru că nu au de fapt creat un nimic temporară. Care a subliniat la 2. Dacă realocați indicatorul, apoi restul de lista este total pierdut. Deci vrei să fie foarte, foarte atent aici a atribui mai întâi pointer la tot ce doriți să introduceți în oriunde vrei, și apoi poate dereference restul listei. 

Deci, acest lucru este valabil pentru orice destinație sunteți încercarea de a introduce în. Dacă doriți să introduceți la cap, dacă doriți să răspundeți aici, dacă doriți să introduceți la cele din urmă, ei bine, final am că v-ar doar nu au nici o pointer, dar doriți să vă asigurați că nu pierde restul listei. Mereu doriți să vă asigurați noul nod este îndreptat spre tot ce doresc să introduceți în, și apoi puteți adăuga înlănțuirii pe. Toată lumea clar? 

Acest lucru va fi una dintre problemele reale. Una dintre cele mai importante aspecte ai de gând să aibă pe PSET dvs. este că ai de gând să încercați să creați o listă legată și lucruri Insert dar apoi doar pierde restul lista legate. Și tu vei fi ca, am nu știu de ce acest lucru se întâmplă? Și este o durere de a trece prin și de căutare toate indicii tale. 

Și vă garantez pe acest PSET, scris și de desen aceste noduri din va fi foarte, foarte util. Astfel încât să puteți ține evidența complet de unde toate indicii tale sunt, ce se întâmplă greșit, în cazul în care toate nodurile dumneavoastră sunt, ceea ce trebuie să faceți pentru a accesa sau inserați sau ștergeți sau la oricare dintre ele. Toată lumea bună cu asta? Misto. 

Deci, dacă am vrut să se uite la codul? Oh, nu știu dacă am Puteti vedea the-- OK, deci în partea de sus tot ce este este o funcție numit inserție unde vrem pentru a insera int n în lista legat. Vom trece prin asta. Este o mulțime de cod, o mulțime de noi sintaxă. Vom fi în regulă. 

Deci până la partea de sus, ori de câte ori dorim să creăm ceva ce trebuie să facem, mai ales dacă doresc să nu fi stocate pe stiva dar în grămadă? Mergem la un malloc, nu? Deci vom crea un pointer. Nod, pointer, noi egali malloc de mărimea unui nod pentru că vrem ca nod să fie create. Vrem cantitatea de memorie care un nod preia care urmează să fie alocate pentru crearea de noul nod. 

Și apoi vom verifica la a vedea dacă noi egali egal nul. Amintiți-vă ce am spus? Orice ai malloc, ceea ce trebuie să faci mereu? Trebuie să verificați întotdeauna pentru a vedea sau nu, care este nul. 

De exemplu, în cazul în care dumneavoastră de operare Sistemul a fost complet plin, dacă ați avut nici mai multă memorie la toate și încercați să malloc, ar intoarce null pentru tine. Și așa că, dacă încercați să-l utilizați când a fost îndreptat la nul, nu sunteți de gând să poată pentru a accesa aceste informații. Și astfel, ca atare, ne-am dorit să sigur că ori de câte ori sunteți mallocing, te mereu de verificare pentru a vedea dacă că memoria dat la tine este nul. Și dacă nu e, atunci ne putem muta mai departe cu restul codului nostru. 

Așa că am de gând să inițializa noul nod. Vom face noi n este egal cu n. Și apoi ne-am de gând să faci stabilit noi cursorul pe noua la null pentru că acum nu avem vreau nimic pentru ca aceasta să indice. Nu avem nici o idee unde o să te pun, și apoi, dacă vrem să introduceți-l la cap, atunci putem realoca indicatorul la cap. Are toată lumea să urmeze logica de unde ce se intampla? 

Tot ce facem este de a crea un nou nod, setarea indicatorul de nul, și apoi realocarea l la cap dacă am Știu că vrei să-l introduceți la cap. Și apoi capul se va punctul spre care nou nod. Toată lumea OK cu asta? 

Deci, este un proces în două etape. Trebuie să atribui primul indiferent ce creați. Setați ca pointer la de referință, și apoi poate un fel de dereference prima indicatorul și punctul spre noul nod. Oriunde doriți să-l inserați, că logica este de gând să dețină adevărat. 

E un fel de atribuire variabile temporare. Amintiți-vă, ai pentru a vă asigura că Nu pierde urma, dacă sunteți pompare. Doriți să vă asigurați că aveți o variabilă temporară acest tip de tine urmări în cazul în care acel lucru este depozitat astfel încât să Nu pierde nici o valoare în cursul de cum ar fi în jur de joc cu ea. 

OK, deci codul va fi aici. Voi arunca o privire după secțiune. Acesta va fi acolo. 

Deci cred cum se acest diferă dacă ne-am dorit pentru a introduce în mijlocul sau la sfârșitul? Are cineva are o idee de ceea ce este pseudocod ca referință logică care ne-ar lua dacă ne-am dorit pentru al introduce în mijloc? Deci, dacă am vrut să-l introduceți la cap, tot ce faceți este să creați un nou nod. Am stabilit indicatorul de care nod nou la orice cap, și apoi ne-am stabilit capul la noul nod, nu? Dacă am vrut să-l introducă în mijlocul a listei, ceea ce ar trebui să facem? 

Audiența: Ar fi încă fie un proces similar ca și cum atribuirea pointer și apoi atribuirea că pointer, dar ne-ar trebui pentru a localiza acolo. 

ANDI Peng: Exact, așa exact același proces în afară de tine Trebuie să localizeze unde te doresc ca noi să se deplaseze indicatorul în, așa că dacă vreau să insera în mijlocul legate list-- OK, să spunem că e lista noastră legată. Dacă vrem să-l inserați aici, vom crea un nou nod. Vom malloc. Vom crea un nou nod. Vom fi atribuit pointer de acest nod aici. 

Dar problema care diferă de unde capul este este că am știut exact în cazul în care capul este. Acesta a fost chiar la început, nu? Dar aici avem de a urmări de unde ne-l introduceți în. Dacă suntem introducerea nostru nod aici, avem pentru a vă asigura că un precedent pentru acest nod este cel care reassigns indicatorul. Deci atunci va trebui să fel de urmări două lucruri. Dacă vă urmări în cazul în care acest lucru nod în prezent este introducerea în. Trebuie, de asemenea, pentru a urmări în cazul în care nodul anterior că sunteți în căutarea la a fost de asemenea acolo. Toată lumea bună cu asta? BINE. 

Cum despre introducerea în cele din urmă? Dacă am vrut să-l adăugați here-- dacă aș vrea pentru a adăuga un nou nod la sfârșitul unei liste, cum s-ar putea să merg despre a face asta? Audiența: Deci prezent, a subliniat ultima la null. ANDI Peng: Da. Exact, așa aceasta în prezent este indicat să știe, și așa cred că, în acest sens, este foarte ușor de a adăuga la sfârșitul unei liste. Tot ce trebuie să faceți este să-l setat egală cu null si apoi boom-ul. Chiar acolo, foarte usor. Foarte simplu. 

Foarte similar cu cap, dar în mod logic te doriți să vă asigurați că pașii luați spre a face orice de acest lucru, te în urma de-a lungul. Este foarte ușor să, în mijloc de codul, prins pe, oh, am atât de multe indicii. Nu știu unde ceva se indică spre. Nu știu nici ce nod sunt pe. Ce se intampla? 

Relaxați-vă, calma, să ia o respiratie adanca. Scoate lista dvs. legate. Dacă spui, știu unde Am nevoie de a introduce acest lucru în și știu exact cum să realocați meu indicii, mult, mult mai ușor să-și imagineze out-- mult, mult mai ușor să nu se pierd in bug-uri de codul. Toată lumea OK cu asta? BINE. 

Deci cred un concept pe care nu am într-adevăr a vorbit despre înainte de acum, și te-am ghicit, probabil, nu se va întâlni mult yet-- e un fel de concept-- avansat este că avem de fapt o date structura numita o listă de două ori legată. Deci, ca voi poate vedea, tot ce facem este crearea o valoare reală, un plus de indicatorul pe fiecare din noduri noastre care, de asemenea, puncte de la nodul anterior. Deci, nu numai că ne-am nostru noduri punct la următoarea. Ei, de asemenea punctul de la cel anterior. Am de gând să ignore aceste două chiar acum. 

Deci atunci aveți un lanț care poate muta în ambele sensuri, și atunci este un pic mai ușor să urmeze în mod logic de-a lungul. Ca aici, în loc de urmărirea de, oh, am trebuie să știi că acest nod este cel care trebuie să realocați, Eu pot merge doar aici și doar trage anterior. Atunci știu exact unde care este, și apoi nu trebuie să traverseze elementele listei de legătura. Este un pic mai ușor. 

Dar, ca atare, trebuie de două ori cantitatea de indicii, asta e dublu față de cantitatea de memorie. Este o mulțime de indicii pentru a urmări. Este un pic mai complex, dar este un pic mai mult de utilizat în funcție pe ceea ce încearcă să realizeze. 

Deci, acest tip de date structură există total, și structura este foarte, foarte simplu cu excepția tot ce avea este, în loc de doar un pointer la următorul, aveți, de asemenea un pointer la anterioară. Asta e tot diferența a fost. Toată lumea bună cu asta? Misto. 

Bine, asa ca acum eu sunt să-și petreacă într-adevăr, probabil, ca 15 la 20 minute sau cea mai mare parte a restul timpului în secțiunea vorbesc despre tabele de dispersie. Câți dintre voi au citit spec pset5? Bine, bine. Asta e mai mare decât 50% din normal. E bine. 

Deci, ca voi vedea, esti provocare în pset5 va fi de a pune în aplicare un dicționar în cazul în care încărcați peste 140.000 de cuvinte că vă oferim și verificare a ortografiei se împotriva tot textul. Vă vom da aleatoare piese de literatură. Vă vom oferi Odiseea. Vă vom oferi Iliada. Vă vom oferi Austin Powers. 

Și provocarea va fi de a scrie cec fiecare cuvânt în toate dintre aceste dicționare în esență, cu checker nostru vraja. Și așa sunt câteva piese de a crea acest PSET, în primul rând pe care doriți să fie capabil de a încărca de fapt toate cuvintele dvs. în dicționar, și apoi doresc să fie în măsură să vraja verifica toate. Și astfel, ca atare, ai de gând să solicite o structură de date care pot face acest lucru rapid și eficient și dinamic. 

Deci, cred că cel mai ușor mod de a face acest lucru, ar crea, probabil, o serie, nu? Cel mai simplu mod de depozitare este de tine poate crea o serie de 140.000 de cuvinte și doar le pe toate acolo și puneți apoi traversează le de căutare binară sau prin selecții sau not-- pare rău că e de sortare. Le puteți sorta și apoi le traversa de căutare binară sau Căutare doar liniar și doar finale cuvintele, dar că ia o mare cantitate de memorie, și nu este foarte eficient. 

Și așa vom începe vorbesc despre moduri de a face timpul nostru de funcționare mai eficientă. Și scopul nostru este de a obtine constanta de timp în cazul în care e aproape ca în cazul în care, tablouri aveți acces instantaneu. Dacă aș fi vrut pentru a căuta ceva, Vreau să fie în măsură să doar, boom-ul, se pare exact, și trageți-l afară. Și astfel o structură în care vom deveni foarte aproape a putea accesa constantă timp, această Sfântul Graal în programarea constant timp este numit un tabel hash. Și astfel David menționat anterior [Inaudibil] un pic în curs, dar vom într-adevăr se arunca cu capul în adâncime în această săptămână pe o piesă care în ceea ce privește cum funcționează un tabel hash. 

Deci modul în care un hash lucrări de masă, de exemplu, dacă am vrut pentru a stoca o mulțime de cuvinte, un grămadă de cuvinte în limba engleză, Am putea pune, teoretic, banane, mere, kiwi, mango, pereche, și pepene galben toate doar pe o matrice. Acestea ar putea potrivi toate în și să fie găsiți. Ar fi un fel de o durere de căuta prin și de acces, dar cale mai ușoară de a face acest lucru este pe care le poate crea de fapt o structură numit un tabel hash care ne hash. Vom rula toate cheile prin o funcție hash, o ecuație, care-le pe toate se transformă în un fel de valoare că atunci putem stoca pe în esență, o serie de liste legate. 

Și astfel aici, dacă ne-am dorit pentru a stoca cuvinte în limba engleză, am putea eventual doar, eu nu știu, rândul său, toate primele litere într-un fel a unui număr. Și astfel, de exemplu, în cazul în care mi-am dorit O să fie sinonim cu apple-- sau cu indicele de 0, și B pentru a fi sinonim cu 1, putem avea 26 de intrări care poate stoca doar toate literele alfabet că vom începe cu. Si atunci putem avea mere la indicele de 0. Putem avea banane la indicele de 1, pepene galben la indicele de 2, și așa mai departe și așa mai departe. Și astfel, dacă am vrut să căutare hash meu de masă și de acces de mere, Știu de mere începe cu o A, și știu exact că trebuie să fie și hash masa la index 0, deoarece de funcția atribuită anterior. 

Deci, eu nu știu, suntem un program de utilizator în cazul în care veți fi taxat cu nu arbitrarily-- arbitrar, cu încercarea de a gînditor cred că de ecuații bune să fie capabil să se răspândească din toate valorile într-un fel, ei pot accesa cu ușurință mai târziu la o ecuație cu ca pe care le, le știu. Deci, în sensul dacă am vrut să merg la mango, știu, oh, aceasta începe cu m. Acesta trebuie să fie la indicele de 12. Nu trebuie să căutați prin nimic. Știu exactly-- am putea merge doar la indicele de 12 și trageți asta. 

Toată lumea clar cu privire la modul de Funcția de tabelă hash funcționează? E un fel de doar o gamă mult mai complex. Asta e tot ce este. BINE. 

Deci cred că rula în această problemă de ceea ce se întâmplă dacă aveți mai multe lucruri care vă oferă același index? Deci, spune funcția noastră, tot ce a făcut a fost că prima literă ia și să se întoarcă că într-o respectiv de la 0 la 25 index. Asta e cu totul în regulă dacă ai doar unul din fiecare. Dar al doilea a începe având mai mult, ești Va trebui ceea ce se numește o coliziune. 

Deci, dacă am încerca să introduceți îngropa într-un hash tabel care are deja banane pe ea, ce se va întâmpla atunci când încercați să introduceți asta? Lucruri rele pentru că banana există deja cadrul indicelui pe care doriți să-l stocați în. Berry fel de este ca, ah, ce să fac? Nu știu unde să mă duc. Cum pot rezolva această? 

Și așa voi va fel de vezi facem chestia asta complicat unde putem fel de efectiv crea lista legat în matrice noastre. Și astfel cel mai simplu mod să se gândească la acest lucru, toate tabel hash este un serie de liste legate. Și astfel, în acest sens, aveți această matrice frumos de indicii, și apoi fiecare indicator în această valoare, în acest index, poate indica de fapt, la alte lucruri. Și astfel încât să aveți toate aceste separat lanțurile care vin de pe o mare matrice. 

Și astfel aici, dacă am a vrut să introduceți Berry, Știu, bine, am de gând pentru a introduce aceasta prin funcția mea hash. Am de gând să se încheie cu indicele de 1, și apoi am de gând să fie în măsură să aibă doar un subset mic de acest gigant Dicționar 140.000 de cuvinte. Și apoi mă pot uita doar prin 1/26 de asta. 

Și așa atunci eu pot insera doar Berry fie înainte, fie după banana în acest caz? După, nu? Și așa ai de gând să doriți să inserați acest nod după banane, și așa vei introduce la coada acestei liste legate. Am de gând să mă întorc la acest diapozitiv anterior, astfel încât voi puteți vedea cum funcție hash funcționează. 

Deci funcție hash este această ecuație că rulați un fel de intrare dvs. prin pentru a obține, indiferent de index doriți să-l atribuiți spre. Și astfel, în acest exemplu, toate ne-am dorit pentru a face a fost să ia prima literă, rândul său, că într-un index, apoi ne poate stoca că în funcția noastră hash. Tot ce facem aici este că suntem conversia prima literă. Deci keykey [0] este doar prima literă indiferent de string avem, ne trece în. Suntem de conversie care la partea superioară, și suntem scăderea de majuscule A, deci tot ce este de a face dă-ne un număr în care putem hash valorile noastre pe. 

Și apoi vom reveni hash SIZE modul. Fiți foarte, foarte atent pentru că, teoretic, aici valoarea ta hash ar putea fi infinit. Ar putea merge doar pe și de pe și de pe. Ar putea fi ceva cu adevărat, într-adevăr de mare valoare, ci pentru că tabelul hash care ați creat are doar 26 de indici, doriți să vă asigurați că modulusing astfel încât să Nu run-- este la fel lucru ca queue-- dvs. astfel încât să nu a alerga pe partea de jos a funcției hash. 

Vrei să-l încheie în jurul valorii de spate în același mod în [Inaudibil] atunci când ai avut ca un foarte, scrisoare foarte mare, vă nu a vrut asta doar rulați de pe la sfârșitul. Acelasi lucru aici, pe care doriți să vă asigurați aceasta nu se execută de pe la sfârșitul de ambalaj în jurul la partea de sus a tabelului. Deci, aceasta este doar o foarte funcție hash simplă. Tot ce a făcut a fost să ia primul scrisoare de orice intrare noastre a fost și să se întoarcă că într-un index care am putea pune în masa noastră hash. 

Da, și așa cum am spus mai înainte, modul în care ne rezolva coliziuni în hash nostru tabele sunt cu, ceea ce noi numim, înlănțuirea. Deci, dacă încercați să introduceți mai multe cuvinte care incep cu același lucru, ai de gând să aibă o valoare hash. Avocado și mere, dacă ați rulați-l prin funcția noastră hash, sunt de gând să vă dau același număr, numărul de 0. Și astfel modul în care rezolva, care este că putem de fapt un fel de le lege împreună prin liste legate. 

Și astfel, în acest sens, voi poate vedea un fel de modul in care structurile de date care am fost de stabilire anterior ca o stafidă legat listă fel de pot veni împreună într-o singură. Și apoi puteți crea departe structuri de date mai eficiente care se pot ocupa sume mai mari de date, care redimensiona dinamic în funcție de nevoile dumneavoastra. Toată lumea clar? Toată lumea fel de clare pe ceea ce se întâmplă aici? 

Dacă aș fi vrut să insert-- ceea ce este un fructe, care începe cu, nu știu, B, altele decât Berry, banana. 

Audiența: Blackberry. 

ANDI Peng: Blackberry, mure. În cazul în care nu merge blackberry aici? Ei bine, am de fapt, nu am sortat acest lucru încă, dar teoretic dacă ne-am dorit să avem această în ordine alfabetică, în cazul în care ar trebui să meargă BLACKBERRY? 

Audiența: [inaudibil] 

ANDI Peng: Exact, după aici, nu? Dar din moment ce este foarte dificil de a reorder-- Cred că depinde de voi. Voi poate total punerea în aplicare a ceea ce vrei. Mai mult eficient mod a face acest lucru, probabil, ar fi pentru a sorta legate dumneavoastră lista în ordine alfabetică, și așa mai departe atunci când sunteți inserarea lucruri, pe care doriți pentru a fi sigur de a le insera în ordine alfabetică astfel încât atunci când ești încercarea de a le căuta, nu trebuie să traverseze tot. Știi exact unde este, și este mai ușor. 

Dar, dacă aveți un fel de lucruri intercalate aleator, sunteți încă de gând să aibă să-l traverseze oricum. Și așa, dacă am vrut să doar introduceți blackberry aici și am vrut pentru a căuta ea, știu, oh, mure trebuie să înceapă cu indicele de 1, asa ca am știu instantaneu doar de căutare la 1. Și apoi pot fel de traversa lista legată până ajung la Blackberry, și then-- da? 

Audiența: Dacă sunteți încercarea de a create-- Cred că acest lucru este o ca hash foarte simplu funcţie. Și dacă ne-am vrut să fac mai multe straturi de care cum ar fi, OK, vrem să se separe în la fel ca toate literele alfabetice și apoi din nou să-i placă un alt set de scrisori alfabetic în care, ne pune ca un hash tabel într-un tabel hash, sau ca o funcție într-o funcție? Sau este that-- 

ANDI Peng: Deci hash-ul function-- masa ta hash poate fi la fel de mare ca și doriți să-l. Deci, în acest sens, m-am gândit a fost foarte usor, foarte simplu pentru mine pentru a bazat doar un fel pe scrisori de primul cuvânt. Și deci nu e doar 26 de opțiuni. Nu pot sa ma doar 26 de opțiuni din 0 până la 25, deoarece acestea pot doar începe de la A la Z. Dar dacă ai vrut pentru a adăuga, probabil, o mai mare complexitate sau mai rapid a alerga timp pentru dvs. tabel hash, absolut pot face tot felul de lucruri. Puteți face propriul ecuație care vă oferă mai mult de distribuție în ta cuvinte, atunci când căutați, o să fie mai rapid. 

Este complet până la voi modul în care doriți să pună în aplicare acest lucru. Ganditi-va ca doar galeti. Dacă am vrut să am 26 găleți, am de gând pentru a sorta lucrurile în aceste galeti. Dar am de gând să aibă o grămadă de lucruri în fiecare compartiment, deci, dacă doriți să-l facă mai rapid și mai eficient, lasă-mă să o sută de găleți. 

Dar atunci va trebui să găsească o modalitate de a sorta lucrurile, astfel încât acestea sunt în găleată corespunzătoare ar trebui să fie în. Dar atunci când de fapt vrei să te uiți la asta găleată, e mult mai repede, deoarece nu există lucruri mai puțin în fiecare compartiment. Și astfel, da, asta e de fapt truc pentru voi în pset5 este că vei contestat de a crea doar ceea ce este cel mai eficient Funcția vă puteți gândi de a fi capabil să stocheze și să verifice aceste valori. 

În totalitate până la voi Cu toate acestea vrei sa o faci, dar asta e un punct foarte bun. Că tipul de logica tine doresc să înceapă să se gândească despre este, ei bine, de ce nu am face mai multe galeti. Și atunci am să caute mai puțin lucruri, și atunci poate am au o funcție hash diferit. 

Da, există o mulțime de moduri de a face acest lucru PSET, unele sunt mai repede decât altele. Sunt total de gând pentru a vedea cât de rapid a fost cel mai rapid voi va să poată obține funcțiile la locul de muncă. OK, toată lumea de pe bun tabele înlănțuirea și hash? Este de fapt foarte simplu ca un Conceptul dacă te gândești la asta. Tot ce este este separarea indiferent intrări tale sunt în găleți, sortarea lor, iar apoi căutarea listele care nu este asociat cu. 

Misto. Bine, acum avem un alt fel de structură de date care se numește un copac. Să mergem mai departe și vorbim despre încercări care sunt distinct diferite, dar în aceeași categorie. În esență, toate un copac este în schimb de organizare a datelor în mod liniar că un tabel hash te does-- Știi, e luat un top și un fund și apoi un fel de legături de pe o it-- copac are un top care te sun rădăcină, și apoi are frunze tot în jurul ei. 

Și astfel tot ce trebuie aici este doar nodul de sus care indică spre alte noduri, că punctele la mai multe noduri, și așa mai departe și așa mai departe. Și așa trebuie doar ramuri de divizare. Este doar un mod diferit de organizare date, și pentru că am un copac apel, voi doar-- e doar modelat la arate ca un copac. De aceea o numim copaci. 

Tabelul Hash arata ca un tabel. Un copac doar arata ca un copac. Tot ce este este un separată mod de organizare noduri în funcție de ceea ce sunt nevoile dumneavoastra. 

Astfel încât să aibă o rădăcină și atunci aveți frunze. Modul în care putem special cred despre acesta este un arbore binar, un arbore binar este doar o tip specific de un copac în cazul în care fiecare nod doar puncte la, la max, alte două noduri. Și astfel aici aveți distinct simetrie în arborele care face mai ușor să se uite un fel de la ce valori ești pentru că atunci au întotdeauna un stânga sau la dreapta. Nu e niciodată ca o treime din stânga stânga sau sfert din stânga. E doar ai un stânga și un drept și puteți căuta oricare dintre cei doi. Și așa de ce este acest util? Modul în care acest lucru este util este dacă sunteți în căutarea pentru a căuta prin valori, nu? Mai degrabă decât de punere în aplicare binare căutare într-o matrice de eroare, dacă ai vrut să fie în măsură de a introduce noduri și ia noduri după bunul plac și, de asemenea păstra căutarea capacități de căutare binară. Deci, în acest fel, suntem un fel de tricking-- amintesc când am a declarat liste legate nu poate căuta binare? Suntem un fel de a crea o structură de date că trucuri care în lucru. 

Și liste așa că legate sunt liniare, ele se leagă numai una după alta. Putem avea un fel de diferită de indicii fel acel punct la diferite noduri care ne poate ajuta cu căutare. Și astfel aici, dacă am vrut să au un arbore binar de căutare, Știu că de mijloc mea, dacă 55. Mă duc pentru a crea acea ca mijloc mea, ca root meu, și apoi am de gând să aibă Valorile spin off de ea. 

Deci, aici, dacă am de gând pentru a căuta valoarea de 66, eu pot începe la 55. E 66 mai mare decât 55? Da, este, așa că știu că mus căutare I n indicatorul din dreapta a acestui copac. Mă duc la 77. OK, este mai mică de 66 sau mai mare de 77? E mai puțin de, ca să știi, oh, care trebuie să fie nodul din stânga. 

Și astfel aici suntem un fel de conservare toate lucrurile mari despre tablouri, așa cum ar fi redimensionarea dinamică de obiecte, fiind posibilitatea de a insera și șterge în voie, fără a fi nevoie să vă faceți griji cu privire la tip fix cantitate de spațiu. Noi încă păstra toate aceste lucruri minunate în același timp, de asemenea, posibilitatea de a păstra jurnal și ora de căutare binare de căutare că am fost doar anterior posibilitatea de a obține o frază. 

Structură de date rece, un fel de de implementat, nodul. După cum puteți vedea, tot ce este struct nodului este că aveți o stânga și un pointer drept. Asta e tot ce este. Deci, mai degrabă decât doar având o x sau un precedent. Aveți un stânga sau dreapta, apoi puteți fel de link-ul împreună Aveți însă asa ca alege. 

OK, vom merge de fapt să ia doar câteva minute. Deci vom întoarce aici. Așa cum am spus mai înainte, Am facut un fel de explicat logica din spatele modul în care ar căuta prin asta. Vom încerca pseudocoding acest lucru pentru a vedea dacă putem fel de aplicați aceeași logică de căutare binară la un alt tip de structură de date. Dacă vreți să luați ca un cuplu minute să se gândească doar despre asta. BINE. Bine, am de gând să de fapt, da doar the-- nu, vom vorbi despre Pseudocodul primul. Deci, nimeni nu vrea pentru a da o lovitură de cuțit la ceea ce primul lucru pe care doriți să facă atunci când te început căutarea este? Dacă căutăm valoarea 66, ceea ce este primul lucru pe care vrem sa facem dacă vrem în binar a căuta acest copac? 

Audiența: vrei să te uiți drept si uita-te la stânga și se vedea [neauzit] mai mare număr. 

ANDI Peng: Da, exact. Deci ai de gând să se uite la rădăcină ta. Există o mulțime de modalități în care puteți apela aceasta, poporul tău nod părinte spune. Îmi place să spun că rădăcină asta e ca rădăcina copacului. Vei să se uite la nodul rădăcină, și tu ești va pentru a vedea este de 66 mai mare sau în minus față 55. Și dacă e mai mare decât, bine, aceasta este mai mare decât, în cazul în care vrem să se uite? În cazul în care vrem să căutați acum, nu? Vrem pentru a căuta în jumătate din dreapta a acestui copac. 

Deci avem, convenabil, o pointer care indică spre dreapta. Și astfel, atunci putem stabili noul nostru rădăcină să fie 77. Putem merge doar la oriunde indicatorul este îndreptat. Ei bine, oh, aici suntem de pornire la 77, si putem doar face acest lucru recursiv nou și din nou. În acest fel, vă fel de au o funcție. Ai un mod de a căuta pe care le poate repeta doar peste si peste si peste, în funcție de cazul în care doriți să căutați până când veți obține în cele din urmă la valoarea pe care le căutați pentru. Are sens? 

Sunt pe cale să-ți arăt real cod, și este o mulțime de cod. Nu este nevoie să sperii. Vom vorbi prin ea. 

De fapt nu. Asta a fost doar pseudocod. OK, că a fost doar Pseudocodul, care este un complex pic, dar este absolut în regulă. Toată lumea în urma de-a lungul aici? Dacă rădăcina este nul, întoarcerea fals, pentru că mijloacele tu nici măcar nu au nimic acolo. 

Dacă rădăcină n este valoarea, deci, dacă aceasta se întâmplă să fie cel ce te uiți, atunci ai de gând să se întoarcă adevărat pentru că știi că găsit-o. Dar dacă valoarea este mai mică decât rădăcină de n, ești merge pentru a căuta stânga copil sau frunza din stânga, ce vrei să-i spunem. Iar dacă valoarea este mai mare decât rădăcină, ai de gând să căutați copac corect, apoi executați doar funcția prin căutare din nou. 

Și dacă rădăcina este nul, că această înseamnă că ai ajuns la sfârșitul? Asta înseamnă că nu aveți nici o mai multe frunze pentru a căuta, atunci știi, oh, am Cred că nu e aici pentru că după ce am uitat prin totul și nu este aici, pur și simplu nu ar putea fi aici. 

Asta face sens pentru toată lumea? Deci e ca si cum de căutare binară conservarea capacitățile de liste legate. Se răcește, și așa mai departe al doilea tip de voi structura de date baieti Puteți încerca de punere în aplicare pe PSET dumneavoastră, trebuie doar să aleagă o metodă. Dar poate o metodă alternativă de a tabelul hash este ceea ce noi numim un trie. 

Toate un trie este un anumit tip de copac care are valori care merg la alte valori. Deci, în loc de a avea un binar copac în sensul că un singur lucru poate indica două, puteți avea punct un singur lucru la multe, multe lucruri. Aveți în esență, tablouri interiorul care să stocați indicii care indică alte matrice. 

Deci nodul de modul în care ar defini un trie este vrem să avem o Boolean, C cuvânt, nu? Deci nodul este Boolean cum ar fi adevărat sau fals, în primul rând în fruntea că matrice, este aceasta un cuvânt? În al doilea rând, doriți să aveți indicii la orice restul dintre ele sunt. Un complex pic, un pic abstract, dar Voi explica ce că toate mijloacele. 

Deci, aici, în partea de sus, dacă au o serie declarat deja, un nod în cazul în care aveți un Boolean valoarea stocată în față care vă spune este acest cuvânt? Nu este acesta un cuvânt? Și atunci aveți restul de matrice dvs., care de fapt, stochează toate posibilități de ceea ce ar putea fi. Astfel, de exemplu, cum ar fi în partea de sus ai primul lucru pe care spune adevărate sau false, da sau nu, acesta este un cuvânt. 

Și apoi trebuie de la 0 la 26 de literele pe care le puteți stoca. Dacă aș fi vrut să caute aici pentru BAT, mă duc la partea de sus și mă uit pentru B. găsesc B în mea matrice, și așa știu, OK, este un cuvânt B? B nu este un cuvânt, așa că astfel Trebuie să continuați căutarea. Mă duc la B, și mă uit la indicatorul care arată spre B și văd un alt gamă largă de informații, aceeași structură pe care am avut-o înainte. 

Și here-- oh, următoarea scrisoare în [neauzit] este A. Deci, ne uităm în matrice. Găsim a opta valoarea, și apoi ne să vedem, oh, Hei, este că un cuvânt, este B-A-un cuvânt? Acesta nu este un cuvânt. Trebuie să continui să cauți. 

Și așa, atunci ne uităm la cazul în care indicatorul de A puncte, și puncte de la un alt mod în pe care o avem mai multă valoare stocată. Și, eventual,, ajungem la B-A-T, care este un cuvânt. Și astfel încât data viitoare te uiți, te duci să aibă ca verificare, da, Această funcție booleană este adevărat. Și astfel, în sensul că suntem un fel de a avea un copac cu matrice. 

Deci atunci puteți tip de căutare în jos. Mai degrabă decât o funcție și hashing atribuirea de valori de listă legate, puteți pune în aplicare doar o trie care caută downwords. Într-adevăr, într-adevăr lucruri complicate. Nu este ușor să se gândească la, deoarece eu sunt ca scuipa atât de multe structuri de date din la tine, dar nu toată lumea un fel de să înțeleagă cum funcționează logica asta? 

Bine, in regula. Așa B-A-T, și apoi ai de gând pentru a căuta. Data viitoare când te duci pentru a vedea, oh, hei, e adevărat, astfel Știu că trebuie să fie un cuvânt. 

Același lucru pentru Zoo. Deci, aici e un lucru chiar acum, dacă am a vrut pentru a căuta zoo, chiar acum, în prezent, este o grădină zoologică nu cuvânt în dicționarul nostru pentru că, așa cum voi puteți vedea, primul loc ca avem o Boolean return true este la sfârșitul zoom. Avem Z-O-O-M. 

Și astfel aici, nu avem de fapt cuvântul, gradina zoologica, în dicționarul nostru pentru că această casetă de selectare nu este bifată. Deci calculatorul nu stiu ca zoo este un cuvânt pentru că modul în care ne-am stocate ea, doar un zoom aici de fapt, are o valoare Boolean care a fost transformat adevărat. Deci, dacă vrem să introduceți CD-ul cuvânt, grădină zoologică, în dicționarul nostru, cum ne-am merge despre a face asta? Ce trebuie să facem pentru a vă asigura nostru calculator știe că Z-O-O este un cuvânt și nu primul cuvânt este Z-O-O-M? 

Audiența: [inaudibil] 

ANDI Peng: Exact, am doriți să vă asigurați că această aici, că valoarea Boolean este verificat la e adevărat. Z-O-O, atunci vom verifica dacă, așa că știm exact, hei, gradina zoologica este un cuvânt. Am de gând să-i spuneți computer care este un cuvânt atât de că, atunci când controalele de calculator, se știe că grădină zoologică este un cuvânt. 

Deoarece ne amintim toate aceste date structuri, este foarte ușor pentru noi să spun, oh, liliac e un cuvânt. Zoo este un cuvânt. Zoom e un cuvânt. Dar atunci cand esti o clădire, computerul are nici o idee. 

Deci, va trebui să-l spun exact la ce punct este aceasta un cuvânt? La ce punct nu este un cuvânt? Și la ce punct îmi trebuie să caute lucruri, și la ce punct am nevoie pentru a merge mai departe? Toată lumea clar de asta? Misto. 

Și astfel apoi vine problemă de cum ne-ar du-te despre inserarea ceva asta nu e de fapt acolo? Deci, hai să spunem că doriți să introduceți cuvântul, baie, în trie nostru. După cum voi putea vedea ca in prezent tot ce avem acum este B-A-T, și această nouă structură de date acolo a avut o halbă care a subliniat null pentru că presupunem că, oh, nu e fără cuvinte după B-A-T, de ce avem nevoie pentru a păstra având lucruri după care T. 

Dar problema apare dacă facem te doresc să aibă un cuvânt care vine după lui T. Dacă aveți de baie, ești de gând să doriți un drept H. Și astfel modul în care vom face acest lucru este vom crea un nod pentru a separat. Nu ne aloca orice sumă de memorie pentru această nouă serie, si vom realoca indicii. 

Vom fi atribuit H, întâi de toate, acest null, vom scăpa de. Vom avea cele descendentă litera h. Dacă vom vedea o H, l-am dori pentru a merge în altă parte. 

În aici, putem verifica apoi pe Da. Dacă ne-am lovit un H după T, oh, atunci știm că acest lucru este un cuvânt. Boolean va reveni adevărat. Toată lumea clar cu privire la modul sa întâmplat? BINE. 

Deci, în esență, toate aceste structuri de date că am trecut peste ziua de azi, am trecut peste ele foarte, foarte repede și nu în prea mult detaliu, și asta e în regulă. Odată ce ați începe încurcați cu el, vei urmărirea în cazul în care toate indicii sunt, ce se întâmplă în dumneavoastră structuri de date, etc.. Vor fi foarte util, și este de până la tine voi să dau totul cum pe care doriți să pună în aplicare lucrurile. 

Și astfel pset4, de 5-- oh, că este greșit. Pset5 este greșeli de ortografie. Așa cum am spus mai înainte, ai de gând să, o dată din nou, descărca codul sursă de la noi. Nu va fi de trei principale lucruri veți fi descărcarea. Veți descărca dictionare, KERS, și texte. 

Toate aceste lucruri sunt sunt fie dicționare de cuvinte pe care ne-o dorim să verificați sau test de informații pe care ne-o dorim sa verificarea ortografică. Și astfel dicționarele dăm aveți de gând pentru a vă oferi cuvinte reale pe care ne-o dorim să stocați într-un fel într-un mod care este mai eficient decât un tablou. Și apoi textele sunt Va fi ceea ce suntem care vă solicită să prezinte asigurați-vă că toate cuvintele sunt cuvinte reale. 

Și astfel cele trei blocuri de programe pe care le vom oferi sunt numite dictionary.c, dictionary.h, și speller.c. Și atunci tot dictionary.c nu este ceea ce a cerut să pună în aplicare. Se încarcă cuvinte. Se scrie cecuri lor, și-l face sigur este introdusă corect ca totul. 

diction.h este doar un fișier bibliotecă că declară toate aceste funcții. Si speller.c, vom să vă dau. Nu aveți nevoie de a modifica nimic. Toate speller.c nu este să ia că, loturile aceasta, verifică viteza de ea, testează referință de ca și cum repede sunteți în stare să facă lucruri. 

Este un Speller. Doar nu te pui cu el, dar face vă că ați înțeles ce face. Noi folosim o functie numita getrusage care testează performanța vraja ta checker. Tot ce face este, în principiu testa timp de totul în dicționarul, astfel încât asigurați-vă că înțelege. Fii atent pentru a nu te pui cu ea sau celelalte lucruri nu se va executa în mod corespunzător. 

Și cea mai mare parte a acestei provocări este pentru voi de a modifica într-adevăr dictionary.c. Vom să vă dau 140.000 de cuvinte în dicționar. O Vom să vă dau un text fișier care are aceste cuvinte, și vrem să fie în măsură să organizeze le într-un tabel hash sau o trie pentru că atunci când cerem să scrie check-- imagina daca esti vraja verificarea ca Odiseea lui Homer. E ca și cum acest test enorm, imens. 

Imaginați-vă dacă fiecare cuvânt pe care a trebuit să se uite printr-o serie de 140.000 de valori. Asta ar lua pentru totdeauna pentru masina dvs. pentru a rula. De aceea dorim să organizăm nostru date în structuri de date mai eficiente cum ar fi un tabel hash sau o trie. Și apoi voi putea fel de atunci când căutați acces lucrurile mai ușor și mai rapid. 

Și astfel încât să fie atent pentru a rezolva coliziuni. Vei obține o grămadă de cuvinte de care încep cu A. Vei obține o grămadă de cuvinte care începe cu B. Până la tine baieti modul în care doriți să-l rezolve. Poate e mai mult funcție hash eficientă decât doar prima literă a ceva, și pentru ca depinde de tine voi să fel de a face ce vrei. 

Poate doriți să adăugați toate scrisorile împreună. Poate vrei să faci lucruri ciudate plac pentru a ține cont de numărul de litere, tot ceea ce. Până la voi cum vă doriți să faceți. Dacă vrei să faci un tabel hash, dacă doriți să încercați un trie, în totalitate până la tine. Am să vă arăt înainte de momentul în care trie este de obicei un pic mai dificil doar pentru că există o mulțime mai multe indicii pentru a urmări. Dar în totalitate până la voi. Este mult mai eficient în cele mai multe cazuri. Vrei să fii cu adevărat capabil să țină evidența tuturor indicii tale. Ca face acelasi lucru ca am fost aici. Când sunteți încercarea de a introduce valorile într-un tabel hash sau șterge, asigurați-vă că sunteți păstrarea într-adevăr piesa de unde totul se datorează faptului că este foarte ușor pentru că dacă eu sunt încercarea de a introduce ca cuvântul, Andy. Să spunem doar că este o cuvânt reală, cuvântul, Andy, într-o listă gigant de o cuvinte. 

Dacă doar se întâmplă să realocați un pointer greșit, Oops, acolo se duce în întregime de restul de lista mea legată. Acum, singurul cuvânt am au este andy, iar acum toate celelalte cuvinte în Dicționar s-au pierdut. Și așa doriți să vă asigurați că ține evidența tuturor indicii dvs. sau altceva ai de gând să obțineți Probleme uriașe în codul dumneavoastră. Trage lucrurile cu atenție pas cu pas. Se face mult mai ușor să se gândească la. 

Și, în fine, pe care doriți să fie în măsură să testa performanța de programul pe placa de mare. Dacă voi lua o uita-te la CS50 chiar acum, avem ceea ce se numește consiliul mare. Este foaia de arbitraj dintre cele mai rapide vraja ori verificarea pe toate CS50 chiar acum, cred că în partea de sus ca 10 ori cred că opt dintre ele sunt personal. Vrem cu adevărat să voi să ne bată. 

Toate dintre noi au încercat să pună în aplicare cel mai rapid codul posibil. Vrem ca voi să încerce să conteste ne și punerea în aplicare mai repede decât noi toți poate sa. Și așa este într-adevăr acest lucru prima dată când suntem cere voi să faceți un PSET care poți să faci cu adevărat în orice metodă tu vrei. 

Eu spun mereu, acest lucru este mai asemănător la o soluție din viața reală, nu? Eu spun, hei, am nevoie de tine pentru a face acest lucru. Construi un program care face acest lucru pentru mine. Fă-o cum vrei. Știu doar că vreau să postească. Asta e provocarea pentru această săptămână. Băieți, vom pentru a vă oferi o sarcină. Vom pentru a vă oferi o provocare. Și apoi este de până la voi pentru complet doar dau seama ceea ce este cel mai rapid și cel mai mult modalitate eficientă de a pune în aplicare acest lucru. Da? 

Audiența: Avem voie sa dacă A vrut să cercetare moduri mai rapide de a face tabele de dispersie on-line, putem face că și citează cod altcuiva? ANDI Peng: Da, în regulă. Deci, dacă voi citi spec, există o linie în spec care spune voi sunt complet lipsite de cercetare hash funcțiile in care sunt unele funcțiilor hash mai repede pentru a rula lucruri prin ca timp cât vă cita acest cod. Deci, unii oameni au deja a dat seama moduri rapide de a face dame vraja, de rapid modalități de stocare a informației. În totalitate până la voi, dacă doresc să ia doar asta, nu? Asigurați-vă că a cita. Provocarea aici într-adevăr că încercăm să testeze este de a face sigur că știți ți de drum în jurul valorii de pointer. În măsura în care punerea în aplicare a funcția propriu-zisă hash și vine cu ca matematica a face acest lucru, voi poate de cercetare, indiferent de Metodele on-line vreți. Da? 

Audiența: Putem cita doar folosind [neauzit]? 

ANDI Peng: Da. Puteți doar, în comentariu, puteți cita ca, oh, luate de la bla, bla, bla, funcție hash. Oricine are orice întrebări? Noi de fapt breezed prin secțiunea de astăzi. Eu voi fi aici la răspundă la întrebări, de asemenea. 

De asemenea, așa cum am spus, de birou ore în seara asta și mâine. Spec în această săptămână este de fapt super usor si super scurt pentru a citi. Aș sugera lua o privire, doar citit prin totalitatea ei. 

Și de fapt, vă plimba Zamyla prin fiecare dintre funcțiile aveți nevoie pentru a pune în aplicare, și așa e foarte, foarte clar cum se face totul. Doar să vă asigurați că sunteți urmarirea indicii. Acesta este un PSET foarte provocator. 

Nu e din cauza ca o provocare, oh, conceptele sunt atât de mult mai mult dificil, sau va trebui să învețe atât de mult sintaxă nou drum că ai făcut pentru ultima PSET. Aceasta este dificil, deoarece PSET există atât de multe indicii, și atunci este foarte, foarte usor de dată aveți un bug în cod nu putea pentru a găsi în cazul în care bug-ul este. 

Și atât de completă și credința totală în tine voi să fie în măsură să bată nostru [Inaudibil] ortografii. Nu am de fapt, nu orice mină scris încă, dar eu sunt pe cale de a scrie a mea. Deci, în timp ce scrieți a ta, voi fi scris mea. Am de gând să încerce să facă al meu mai repede decât a ta. Vom vedea cine are cel mai rapid cea. 

Și da, voi vedea tot voi aici marți. Eu va rula un fel ca un atelier PSET. Toate secțiunile acestui săptămână sunt ateliere de lucru PSET, așa voi avea o mulțime de oportunități Pentru ajutor, orelor de program ca întotdeauna, și chiar cu nerăbdare să citirea toate cod băieții tăi. Am teste aici dacă Vreți să vină să cele. Asta e tot.