DAVID MALAN: În regulă. Bine ati venit înapoi la CS50. Acesta este începutul săptămânii 8. Și amintesc că setul problema 5 încheiat cu un pic de o provocare. Deci, presupunând că ați recuperat toate de dvs. Fellows de predare și fotografii CA în fișierul card.raw, vă sunt eligibile pentru a găsi acum toate aceste persoane, și un câștigător norocos va pleca acasa cu unul de aceste lucruri, mișcarea salt dispozitiv pe care le puteți folosi pentru finală proiecte, de exemplu. 

Aceasta, în fiecare an, conduce la un pic de creepiness. Și deci ce m-am gândit face este cota cu voi unele dintre notele care au plecat înainte și înapoi peste lista personalului de întârziere. De exemplu, doar noaptea trecută, citat citatul, de la una din personalul membri, "am avut doar o bătaie elev la ușa mea pentru a face o fotografie cu mine. Stalkers, vă spun ", a început. destul de descriptiv și apoi ne-am mutat pe, o oră sau cam asa ceva mai târziu, "am avut o elev de așteptare pentru mine, după secțiunea și el a avut toate numele noastre și fotografii pe unele foi de hârtie. "În regulă. Deci organizat, dar nu tot ce înfiorător încă. 

Apoi, "am fost plecat din oras in acest weekend, și când m-am întors, era unul din meu dormitor. "[râsete] DAVID MALAN: Următorul citat dintr-un personal membru, "un elev a venit la casa mea de la Somerville la 4 dimineața asta. "Urmatorul personal, "am ajuns la hotel în San Francisco și un student a fost de așteptare pentru ma la lobby-ul cu trei DSLR. " Tip de aparat de fotografiat. "Eu nu sunt nici pe personal acest semestru, dar un elev a intrat în casa mea, această dimineață și a înregistrat totul cu Google sticlă "și apoi. în cele din urmă, "Cel puțin 12 de persoane au fost nerăbdare așteaptă pentru mine când am ieșit din mea limuzina, și apoi am sa trezit. "În regulă. Deci, printre fotografii, cum s-ar putea amintesc, sunt acest om aici, care te- s-ar putea, stiu ca Milo Banana, care locuiește cu Lauren Carvalho, capul nostru predare Fellow. Milo Milo, vin aici băiete. Milo. Milo. Țineți minte, el poartă Google Glass, așa vă vom arăta toate astea după. Deci, aceasta este Milo dacă doriți să să ia o fotografie cu el după aceea. Dacă doriți să se uite la publicul acolo. OK. Asta e filmarea bine. Ei bine, Milo Banana. Oh, nu face asta. 

[Râsete] 

OK. Deci, un cuvânt, apoi pe ceea ce se află înainte, pentru că așa cum vom începe să tranziție, în această săptămână în mod specific, de la C, într-o Mediul linia de comandă a PHP și JavaScript si SQL si HTML și CSS în un mediu bazat pe web, vom fi echiparea vă cu toate mai multe cunoștințe pentru potențiale proiecte finale. Spre acest scop, cursul are o tradiție din organizarea de seminarii care sunt pe teme tangențiale la curs. Foarte mult legate de programare și de app de dezvoltare și așa mai departe, dar nu neapărat explorat de propria programa cursului. 

Deci, dacă ați putea fi interesat într-o singură sau mai mult de seminarii din acest an, înregistrați la cs50.net/seminar. Există seminarii mari la cs50.net/seminars. Și pe lista de până acum pentru acest an sunt Web Apps Amazing cu Ruby pe Șine, care este o alternativă Limba de PHP. Lingvistică Computațională. Introducere în iOS, care este platforma care este folosit pentru iPhone și dezvoltarea iPad. JavaScript pentru Web Apps, vom acoperi care, însă, în acest seminar, veti merge în mai multe detalii. 

Leap Motion, așa că vom avea de fapt, unele de prietenii nostri de la Leap Motion, compania in sine, ni se alature. Maine, de fapt, pentru a oferi un hands-on seminar, dacă de interes pentru tine. Meteor.js, o tehnică alternativă pentru folosind JavaScript nu într-un browser, ci pe un server. Node.js, ceea ce este foarte mult în acest spirit, de asemenea. Elegant Android design. Android fiind o alternativă foarte populară pentru iOS și Windows Phone și alte platforme mobile. Și de securitate Web Active Defense. 

Deci, în fapt, dacă doriți să se angajeze în acest sens, permiteți-mi să face act de acest lucru. Suntem foarte fericiți să spun că prietenii nostri de la Leap Mișcare, care este o pornire - acest dispozitiv într-adevăr venit în urmă cu câteva luni - a donat gratie de 30 de astfel de dispozitive la clasa de cât mai mulți elevi, în cazul în care doriți să împrumute de hardware spre sfârșitul semestrului și-l utilizați pentru un proiect final efectiv. Ei sprijină un număr de limbi. Nici unul dintre ei C, nici unul dintre ei PHP, așa realiza una sau mai multe dintre aceste seminarii s-ar putea dovedi de interes. Și toate acestea vor fi filmate în cazul în care nu sunt în măsură pentru a participa în persoană. Programul fi anuntat prin e-mail ca am solidifica camere. 

Și, în fine, dacă te duci la projects.cs.50.net, acesta este un site web ne menține în fiecare an, pe care vă invităm oameni din comunitate, facultate, departamente, personal, și atât într-un exterior de la CS50 propune idei de proiecte. Lucruri de interes pentru grupurile de studenți. Lucruri de interes pentru departamentele. Deci, nu întoarce acolo, dacă te lupți cu incertitudine cu privire la ceea ce te-ar dori să le rezolve. 

Deci, ultima dată când am introdus-o, fără îndoială, structura de date mai complex decât ne-am văzut în ultimele săptămâni. Am fost folosind tablouri destul de fericit ca un instrument util în cazul în care Structura de date simplist. Apoi am introdus acestea, care Desigur, sunt legate de liste. Și ceea ce a fost una dintre motivațiile pentru introducerea acestei structuri de date? Da? Ce-i asta? 

Audiența: dimensiunea dinamic. 

DAVID MALAN: dimensiunea dinamic. Deci, în timp ce în matrice, trebuie să știu dimensiunea sa, în avans, atunci când îl aloca. În lista de legat, tu nu faci Trebuie să știi că. Puteți doar malloc, sau, mai general, aloce o sumă suplimentară de nod, ca să spunem așa, în orice moment doriți să introduceți mai multe date. Și nodul nu are predeterminat sens. Este doar un termen generic care descrie un fel de container care suntem utilizarea în structura noastră de date pentru a stoca unele element de interes, care, în acest caz se întâmplă să fie întregi. 

Dar există întotdeauna un compromis. Așa că am obține dimensiuni dinamice de date structura, dar ce preț nu plătim? Care e dezavantajul de liste legate? Da? 

Audiența: necesită mai multă memorie. 

DAVID MALAN: Este nevoie de mai mult memorie, cum anume? 

Audiența: [inaudibil]. 

David MALAN: Exact. Deci, acum ne-am indicii inițierea memorie suplimentară pe care le anterior nu au nevoie, pentru că avantajul dintr-o serie, desigur, este faptul că totul e învecinate, înapoi la spate în spate, care vă oferă acces aleator. Pentru că doar prin utilizarea paranteză notație, sau mai multe punct de vedere tehnic indicatorul aritmetică, plus foarte simplu, puteți accesa orice elemente în timp constant. Și, de fapt, asta e un fel de aluzie la un alt pret pe care le plătim cu o Lista legate. 

Ce se întâmplă în timpul de funcționare a ceva de genul căutare, dacă vreau să găsi o anumită valoare și în interior a unei liste legate? Ce devine timpul de funcționare? O mare de n. Dacă este sortate? Ce se întâmplă dacă structura de date este sortat? Pot face mai bine decât mare O a n pentru căutare? Nu, pentru că în cel mai rău caz, s-ar putea foarte bine fi sortate, dar numărul sunteți în căutarea pentru a putea fi mare. Acesta ar putea fi numărul 100, care s-ar putea întâmpla să fie fel, la sfârșitul. Și pentru că puteți accesa doar un legat lista în această punere în aplicare de către mod de primul nod, ai încă un fel de noroc. Trebuie să traverseze totul de la început până la sfârșit, în scopul de a găsi că valoarea mare ca 100. Sau pentru a determina dacă este nici acolo. 

Deci, noi nu putem face ceea ce algoritm într-un datelor structura care arata ca aceasta? Noi nu putem face căutare binară, deoarece binar de căutare necesar pe care am avut acces aleator. Am putea sări doar de la locație la locație, fără a fi nevoie să urmeze aceste firimituri de pâine în formă din toate aceste indicii. 

Acum, cum am pune în aplicare acest lucru? Ei bine, dacă vom merge la ecranul aici, în cazul în care putem reimplementa rapid aceste date Structura - scrisul meu nu e tot ce mare aici, dar vom încerca. Struct astfel typedef, și ce am Vreau să numesc chestia asta aici? Nod. Deci ne intalnim început. Și acum, ceea ce trebuie să fie în interiorul structura de date pentru că individual Lista legat? Cât de multe domenii? 

Deci doi. Una dintre ele este destul de ușor. Deci, int n. Și am putea numi n orice ne dorim, dar ar trebui să fie un întreg, dacă suntem punerea în aplicare a unei liste legate de int. Și acum ce face a doua câmp trebuie să fie? Struct nod *. Deci, dacă am face struct nod *, și apoi am pot apela, de asemenea, acest lucru ce vreau eu, dar doar pentru a fi clar chem o viitoare, așa cum am făcut. Și apoi voi închide bretele mele buclat. 

Și acum, ca și data trecută, Am pus nodul aici. Dar dacă am declarat acest lucru este ca un nod, de ce am deranjat fiind atât de verbose aici, în struct declararea nod * viitor, spre deosebire de la doar nod * viitor? Da? 

Audiența: [inaudibil]. 

DAVID MALAN: Exact. Exact. Deoarece C într-adevăr te duce literalmente și vede numai definiția nodului până aici, nu se poate consultați-l aici. Deci avem acest tip de preemptive declarația de aici, care este, desigur, mai detaliată. Struct nod, ceea ce înseamnă putem accesa acum interiorul structurii de date. 

Și, ca o paranteză, pentru că acest lucru este devenind un pic mai mult subiectiv acum, stele poate merge tehnic aici, se poate merge aici, se poate chiar du-te în mijloc. Am adoptat, în ghidul de stil pentru Desigur, Convenția de punere stele, în imediata vecinătate a datelor tip, care în acest caz, ar fi nod struct. Dar realiza într-o mulțime de manuale și referințe on-line, s-ar putea într-adevăr vezi-l pe partea cealaltă. Dar doar dau seama că ambele vor de fapt locul de muncă și ar trebui să fie pur și simplu consistent. 

Bine. Astfel că a fost declarația noastră de nod struct. Dar apoi am început să facem mai mult lucruri sofisticate. De exemplu, am decis să introducă ceva ca un tabel hash. Deci, aici este un tabel hash de dimensiune N, indexate de la 0 la stânga sus la n minus 1 în partea de jos stânga. Acest lucru ar putea fi un hash de masă pentru nimic. Dar ce fel de lucruri am vorbit despre utilizarea unui tabel hash pentru? Depozitarea ce? 

Nume. Am putea face nume ca am făcut data trecută. Și într-adevăr, puteți stoca nimic. Și vom vedea acest lucru din nou în PHP și JavaScript. Un tabel hash este un fel frumos de Elvețiană Armata cuțit care vă permite să stocați destul de mult tot ce vrei interiorul prin asocierea tastelor cu valori. Taste cu valori. 

Acum, în acest caz simplu, nostru Tastele sunt doar numere. Suntem implementarea unui hash masă ca o matrice. Și așa tastele sunt 0, 1, 2, și așa mai departe. Și astfel noi, ca oameni, a decis ultimul săptămână, că știți ce, dacă suntem merge la numele magazinului, hai să arbitrar, dar destul de rezonabil, presupune că Alice, un nume A, va fi doar indexat în 0. Și Bob, un nume B, vor fi indexate în 1, și așa mai departe. Așa că am avut o cartografiere între intrări, care sunt șiruri, iar distribuire depozite, care sunt numere. 

Astfel că procesul este, în general, cunoscut sub numele de o funcție hash, și puteți cu adevărat l pună în aplicare în cod. Dacă aș fi vrut să pună în aplicare o funcție hash care face exact ceea ce am doar descris la ultima oară, am putea declară o funcție care are, ca intrare, de exemplu - și să facă acest lucru pe acest Ecranul aici. Dacă aș fi vrut să pună în aplicare un hash funcție, am putea spune ceva de genul asta. 

O să se întoarcă un int. Acesta va fi numit hash, și este va accepta ca un argument de șir, sau putem fi mult mai buna acum, și spune char *, vom e numesc. Și apoi toate această funcție are de a face, în cele din urmă, se întoarce un întreg. Acum, cum se face că s-ar putea Nu fi atât de clar. Am de gând să pună în aplicare acest lucru fără nici o forma de verificarea erorilor chiar acum. Mă duc să spun orbește, întoarce tot ce este la s suport 0, minus, să spunem, capitala punct și virgulă. 

Complet rupt. Nu e perfect, deoarece unul, ceea ce în cazul în care s este nul? Lucruri rele se va întâmpla. Doi, ceea ce în cazul în care prima literă din acest Numele nu este o scrisoare de capital? Asta nu se va transforma în bine, fie. Ar putea fi o literă mică sau nu o scrisoare la toate. Deci, în totalitate loc de îmbunătățiri aici, dar aceasta este ideea de bază. 

Ceea ce am descris săptămâna trecută verbal ca doar un proces de cartografiere Alice a 0 și Bob să 1 pot fi exprimate cu siguranță mai mult formulaically ca un C funcționa aici. Chemat din nou hash, are un șir ca intrare, și apoi într-un fel face ceva cu care de intrare pentru a produce o ieșire. Nu spre deosebire de nostru Descrierea cutie neagră pe care le-am facut de mult. Nu știu cum acest lucru ar putea fi lucru sub capota. 

Pentru set de probleme 6, una dintre provocările este pentru tine de a decide ce va fi funcția hash? Ce va fi in interiorul de care negru cutie, și probabil, va fi un mai interesant decât acest lucru, și cu siguranta mai predispuse la erori verificarea decât această special punere în aplicare. 

Dar pot apărea probleme, nu? Dacă avem o structură de date, cum ar fi acest unul, ceea ce este una din problemele puteți rula în timp ce vă introduceți mai multe și mai multe nume în tabela de dispersie? Ai coliziuni, corect? Ce se întâmplă dacă aveți Alice și Aaron, doi oameni ale căror nume sa întâmplat pentru a începe cu A? Care duce la intrebarea, unde pune de-al doilea astfel de nume? 

Ei bine, s-ar putea naivitate doar pune-l unde Bob face parte, dar apoi Bob este fel de înșurubat dacă încercați să inserați numele său viitor și nu e loc pentru el. Deci, s-ar putea pune Bob unde este Charlie, și vă puteți imagina acest lucru foarte repede descentralizarea într-un pic de mizerie. Ceva liniar, în cele din urmă, în cazul în care trebuie doar să caute totul în căutarea de Alice sau Bob sau Aaron sau Charlie. 

Deci, în loc ne-am propus, în loc de doar liniar de sondare pentru spatii deschise și plopping numele acolo, ne- a propus o abordare crescator. Un tabel hash implementat încă cu o serie de indici, dar tipul de date de aceste indicii au fost acum indicii. Trimiteri la ce? Trimiteri la liste legate. 

Deoarece amintesc că o listă de legat este într-adevăr doar un pointer la un nod, și nod are un câmp de lângă, și că nodul are un câmp viitoare, și așa mai departe. Deci, vă puteți gândi acum de această matrice pe în partea din stânga a unui tabel hash ca ceea ce duce la o listă legată. Avantajul de care este dacă aveți un coliziune între Alice și Aaron, ce faci cu doua astfel de persoană? Atașați doar el sau ea pentru a scop, sau chiar la începutul din această listă legat. 

Și, de fapt, hai să Noodle prin că pentru doar o secundă. În cazul în care ar face mai mult sens? Dacă am introduce Alice și ea sfârșește la prima locatie, apoi încerc să inserați numele lui Aaron, și nu e în mod evident o coliziune, ar trebui să pună el la început listei legate? Asta e de la acea prima locație, sau la sfârșit? 

Audiența: [inaudibil]. 

DAVID MALAN: OK. Am auzit început. De ce de la început? 

Audiența: [inaudibil]. 

DAVID MALAN: OK. Este alfabetică, astfel că e frumos. Aceasta este o proprietate bun. Îmi va economisi ceva timp potențial. Nu va lasa-ma sa fac binar de căutare, dar eu ar putea fi capabil de a izbucni cel puțin de o buclă, dacă îmi dau seama, ei bine, eu sunt calea trecut au fost Aaron ar fi în acest sortat listă înlănțuită. Nu am să-mi pierd timpul în căutarea tot drumul până la sfârșit. Așa că e rezonabil. De ce altceva ar putea să doriți să inserați denumirea coliziunea începutul listei? Ce-i asta? 

Audiența: [inaudibil]. 

DAVID MALAN: S-ar putea lua o lungă perioadă de timp pentru a ajunge la sfârșitul listei. Și, de fapt, mai mult și mai mult. Cele mai multe nume pe care le introduce acest începe cu A, cu atât mai mult că lanț este mergi la a lua. Mai mult ca legate Lista este mergi la a lua. Deci, tu ești cu adevărat doar pierzi timpul. Poate că e mai bine menținerea timp de inserare constant, Big O de 1, de a pune întotdeauna numele coliziune la la începutul listei legate, și nu îngrijorătoare la fel de mult de sortare. 

Care este cel mai bun răspuns? Este neclar. Este un fel de depinde de ceea ce distribuție este, ce model este de numele pe care îl inserați. Nu este necesar un răspuns evident. Dar aici sa, din nou, este o oportunitate de design. 

Așa că am apoi se uită la acest lucru, care este într-adevăr altă mare oportunitate pentru p-set 6. Și să realizeze, dacă nu ați făcut deja, Scufundă Zamyla în ambele, hash tabele și încearcă, mai în detaliu. Și walkthrough video este încorporate în p-set spec.. Acest lucru a fost un trie - T-R-I-E. Și ceea ce a fost interesant despre acest lucru a fost faptul că timpul de execuție de a căuta un nume, cum ar fi Maxwell ultima dată, a fost Big O de ce? Ce-i asta? 

Audiența: numărul de litere. 

DAVID MALAN: numărul de litere. Am auzit două lucruri. Numărul de litere și de constanta de timp. Deci, haideți să mergem cu primul. Numărul de litere. Ei bine, această structură de date, amintesc, este ca un copac, un copac de familie, fiecare dintre noduri ale caror sunt formate din matrice. Și aceste matrice sunt indicii pentru alte astfel de noduri, sau alte astfel de matrice în copac. 

Deci, dacă am vrut pentru a determina, atunci dacă Maxwell este aici, s-ar putea merge la prima matrice, la foarte de sus a copac, așa-numitul rădăcină, partea de sus a trie, și apoi urmați indicatorul m, apoi un indicator, atunci x, W, E, L, L. Și apoi, când am vedea unele simbol special, notate aici ca un triunghi. În cod, veți vedea ne-am propus să implementat ca un bool, doar spune da sau nu, un cuvânt se oprește aici. 

Ei bine, odată ce ne-am dus la M-A-X-W-E-L-L, se simte ca șapte, poate opt dacă vom merge cu un trecut, opt pași pentru a găsi Maxwell. Sau să-l K. apel, dar amintesc ultima timp, am susținut că în cazul în care nu există realist o lungime maximă pe o cuvânt, cum ar fi caractere de 40-unele de ciudat, un lungimea maximă implică o valoare constantă. Deci, într-adevăr, da, este punct de vedere tehnic mare O de 8 sau 7, sau într-adevăr mare, O, de K. Dar, în cazul în care există un plafon finit pe care K ar putea fi, este o constantă. Și așa este mare O a 1 la sfârșitul zilei. 

Nu în lumea reală. Nu atunci când începe de fapt, vizionarea ceas ca de funcționare programul dumneavoastră. Este absolut va fi un pic lent decât adevărat constantă timp cu un pas. O să fie șapte sau opt trepte, dar asta e mult, mult mai bine decât un algoritm ca mare O, de n care depinde de dimensiunea a ceea ce este în structură de date. 

Observați susul aici este să putem introduce un milion de nume mai mult în acest structura de date, dar cât de mult mai multe trepte este de gând să ne ia pentru a găsi Maxwell în acest caz? Nici unul. El e afectat. Și până în prezent, eu nu cred că l-am văzut un exemplu al unei structuri de date sau o algoritm care a fost complet neafectat de extern comportamente de genul asta. Dar acest lucru nu poate fi uimitor. Acest lucru nu poate fi singura soluție pentru p-set 

Și nu este. Acest lucru nu este neapărat de date Structura ar trebui sa ajunga, pentru ca tabele de dispersie, compromis. Care este prețul pe care îl plătiți aici? Memorie. Vreau să spun, aceasta este o atroce cantitate de memorie. Și nu se poate vedea destul de aici, deoarece autorul de această imagine evident trunchiat toate matrice, și nu vedem o mulțime de A și Lui B și lui C și a lui Q și lui Y și a lui Z in aceste tablouri. Dar ei sunt acolo. 

Fiecare dintre aceste noduri este o gamă întreagă de circa 26 sau mai mulți octeți, fiecare dintre ceea ce reprezintă o scrisoare. 27, în cazul nostru, astfel încât să putem sprijini Apostrofuri în setul problema. Deci, această structură de date este într-adevăr, foarte dens și larg. Și că numai ar putea ajunge încetinirea lucrurile jos, sau cel puțin vă costă un mult mai mult spațiu. Dar, din nou, se pot trage comparații aici. 

Amintiți-o înapoi în timp, am realizat mult timp mai interesant de funcționare în sortarea atunci când vom folosi îmbinare fel, dar prețul am plătit pentru a realiza n log n pentru îmbinare un fel necesar pe care ne petrecem mai mult ce resurse? Mai mult spațiu. Am nevoie de o gamă secundară a copia persoane în, la fel ca am făcut aici, pe scenă. Deci, din nou, există câștigători clare, ci doar de design subiectiv deciziile să fie luate. 

Bine. Deci, ce zici de asta? Oricine recunoaște pe care D-Hall? OK. Deci, trei dintre noi. Mather House. Deci, aceasta este pentru a lua masa Mather. Pun pariu ca toate sălile de mese au stive de tăvi de genul asta. Și aceasta este de fapt reprezentant de ceva ce am evident, văzut deja. L-am numit pur și simplu o stivă. Și stivă, în termeni de ta memoria calculatorului, este în cazul în care datele se în timp ce funcțiile sunt numite. 

De exemplu, ce fel de lucruri merg pe stiva în ceea ce privește layout-ul de memorie care le-am discutat în ultimele săptămâni? Ce-i asta? 

Audiența: Apeluri la funcții. 

DAVID MALAN: Îmi pare rău. 

Audiența: Apeluri la funcții. 

DAVID MALAN: Apeluri la funcții, dar în mod special, ceea ce este în interiorul fiecăruia dintre aceste cadre? Ce fel de lucruri? Da. Deci variabilele locale. Ori de câte ori am nevoie de unele de stocare locale, ca un argument, sau int i, sau Int temp, sau orice altceva locale variabilă este, am fost pune că pe stiva. Și am o stiva de apel, deoarece de ideea stratificare. Doar un fel de meciuri cu realitatea, conceptul acestuia. 

Dar se pare că o stivă poate, de asemenea, fi văzută ca o structură de date, o alternativă la o matrice, o alternativă la o listă legată. Ceva conceptual mai interesant care pot fi în continuare implementate folosind oricare dintre aceste lucruri, dar e un alt tip de structura de date de sprijin, într-adevăr, doar două operațiuni. Dar puteți adăuga la crescătorul caracteristici decât acestea. Dar acestea sunt elementele de bază - împinge și pop. 

Iar ideea cu un stack este că, dacă am au aici, cu sau fără Annenberg știind, o tavă de lângă ușă cu numărul 9 pe ea. Deci, doar un Int. Și vreau să împingă acest pe date structura, care în prezent este gol. Considera acest jos a stivei. Mi-ar împinge acest număr de 9 pe stivă, iar acum e chiar acolo. 

Dar cel mai interesant lucru despre o stivă este că dacă acum vreau să împingă o alta valoare, cum ar fi 17, și am împinge aceasta pe stiva, am de gând să fac singurul lucru intuitiv, Mă duc să-l pune chiar în cazul în care noi, oamenii, ar fi înclinați să-l pună, pe partea de sus. Dar ceea ce este interesant acum este, cum pot obține de la 9? Știi, eu nu fără un efort. 

Deci, ceea ce este interesant despre o stivă este că de proiectare, este o structură de date LIFO. Mod prostesc de a descrie ultimul, primul plecat. Astfel încât ultimul număr din în acest moment a fost de 17. Deci, dacă vreau să pop ceva off din stivă, acesta poate fi doar 17. Deci, există un ordin obligatoriu de operațiuni aici, unde ultimul element trebuie să fie în primul afară. Prin urmare, acronimul, LIFO. 

Deci, de ce ar fi acest lucru util? Sunt contextele în care te-ar Vreau o structură de date ca asta? Ei bine, a fost cu siguranță utilă în interiorul unui calculator. Sisteme de astfel de operare utilizat în mod clar acest lucru tip de structură de date pentru stive. Vom vedea, de asemenea, aceeași idee atunci când vine vorba de pagini web. Deci, în această săptămână și săptămâna viitoare și dincolo, și cum de a începe punerea în aplicare a web pagini într-un limbaj numit HTML, puteți folosi de fapt, o structură de date ca aceasta pentru a determina dacă pagina este formatat corect. Pentru că vom vedea toate paginile web urmeze un fel de ierarhie, o scobitură care va la sfârșitul zilei, fie, un structură arborescentă sub capota. Astfel mai mult pe faptul că, în doar un pic. 

Dar pentru acum, să propună pentru un clipă, cum am putea merge despre reprezentând ceea ce este o stivă? Permiteți-mi propun să implementăm o stiva cu codul ca aceasta. Deci, o stiva va avea în interiorul ei două lucruri, o matrice, numit tăvi, doar pentru a fi în concordanță cu demo-ul. Și fiecare dintre elementele din care matrice va fi un Int tip. Și capacitatea este probabil ce? Pentru că eu nu am scris definiție completă aici. 

Este, probabil, maxim dimensiunea de matrice. Și este, probabil, a declarat ca un obiect ascuțit definesc în partea de sus a fișierului, unele un fel de constant ca implicite de simpla capitalizare. Deci, undeva capacitate este definită ca dimensiunea maximă posibilă. Intre timp, în interiorul structurii datelor cunoscut ca o stivă va exista fie un întreg cunoscut doar pur și simplu ca dimensiune. 

Deci, dacă ar fi să reprezinte acest lucru acum pictural, să presupunem că această cutie neagră întreg reprezintă stack-ul meu. Interiorul este de două variabile. Așa că am de gând să atragă prima ca mărime. Și a doua am de gând să atragă ca un tablou. 

Dar, doar pentru a menține lucrurile ordonat, în mod normal mi-ar trage-o matrice ca acest lucru, dar este un fel de frumos dacă am corespund realității, sau potrivi cu modelul mental. Deci, lasă-mă în loc să atragă matrice vertical, care este doar, din nou, extrădare artist. Nu contează cu adevărat ceea ce este sub capota. Și vom spune că, în mod implicit, Capacitatea va fi de trei. Deci, acest lucru va fi locația 0, această va fi locația 1, această va fi locația 2. 

Dacă aș mitui cu o minge de stres, ar fi cineva vrea să vină și să rulați bord aici doar pentru o clipă? OK, a văzut mâna întâi. Hai sus. Bine. Deci, eu cred că este Steven. Hai sus. Bine. 

Dar să presupunem că acum suntem înapoi la inițială starea lumii în care am au declarat doar o stiva, și e va fi de capacitate trei. Dar dimensiunea nu a fost încă stabilită. Tăvi nu a fost încă stabilită. Deci, o serie de întrebări în primul rând. Și permiteți-mi să vă dau microfon, astfel încât să puteți participa mai activ în acest sens. 

Deci, ceea ce este în interiorul de dimensiuni în acest moment în timp, dacă tot am făcut este a declarat o stivă cu o linie de cod? 

STEVEN: Nu prea mult. 

DAVID MALAN: OK, nu de mult. Nu știm ce este în interiorul de dimensiuni, nu știm ce e în interior din această matrice aici? 

STEVEN: Doar cod aleatoriu, nu? Doar - 

DAVID MALAN: Da, am de gând să numesc cod, dar aleatoare - 

STEVEN: Lucrurile. 

DAVID MALAN: Lucruri de genul aleatorie 

STEVEN: Bits. 

DAVID MALAN: Bits, corect? Deci valori de gunoi, nu? Deci, permutări de 0 și 1 a lui. Resturi de utilizări anterioare din această memorie. Și nu știm cu adevărat ce valorile sunt, așa că de obicei le trage ca semne de întrebare. 

Deci, primul lucru pe care suntem probabil O să vrei să faci aici - și lasă-mă să dau acest domeniu interior de acolo un nume - tăvi. Ce ar trebui să probabil inițializa dimensiune a dacă vrem să începe să utilizați acest stiva? 

STEVEN: Tava este sub 3. 

DAVID MALAN: Deci, OK. Pentru a fi clar, este declarată capacitatea în altă parte ca trei. Și asta e ceea ce am folosit să aloce matrice. Dimensiunea este de gând să se refere la cât de multe tăvi sunt în prezent pe stiva. 

STEVEN: Zero. 

DAVID MALAN: Deci, ar trebui să fie zero. Așa că mergeți mai departe, și cu orice deget, trage un zero în dimensiune. Bine. Deci, acum, ceea ce este în interiorul acestei aici, nu știm. Acestea sunt de fapt doar valori de gunoi. Deci, am putea desena semne de întrebare, dar Să păstrăm bord curat de acum pentru că nu contează ce-i acolo. Nu avem nevoie pentru a inițializa matrice la nimic, pentru că dacă noi știm că mărimea stivei este zero, bine, ne nu ar trebui să se uita la nimic din această matrice, oricum, la acest moment în timp. 

Deci, acum, să presupunem că am împinge numărul 9 pe stiva. Cum ar trebui să actualizeze structura de date în interiorul acestui cutie neagră? Ce valori trebuie să se schimbe? 

STEVEN: In - dimensiunea? 

DAVID MALAN: OK. Dimensiunea ar trebui să devină ce? 

STEVEN: Dimensiunea ar fi una. 

DAVID MALAN: OK. Deci, dimensiunea ar trebui să devină una. Astfel, puteți face acest lucru în câteva moduri. Permiteți-mi să vă dau, acum dvs. deget este o gumă de șters. Bine. Apoi, acum degetul este o perie. Bine. Și acum ce altceva trebuie să se schimbe, evident, în structura de date? 

STEVEN: Mergem la de jos în sus la 9. 

DAVID MALAN: 9. Bine, bine. Deci, încă nu contează ce e în locație unul sau doi, deoarece acestea sunt Valorile de gunoi, dar noi nu ar trebui să deranjeze caută acolo pentru că dimensiunea este ne spune că numai primul element este, de fapt legitim. Așa că acum am împinge 17 pe lista. Ce se întâmplă cu această imagine? 

STEVEN: Deci, dimensiunea este de gând să meargă la două. 

DAVID MALAN: OK. Ești radieră - oops. Ești o radieră. 

STEVEN: Eraser. 

DAVID MALAN: Esti o perie. 

STEVEN: Brush. 

DAVID MALAN: OK. Și ce altceva? 

STEVEN: Și atunci noi - 

DAVID MALAN: Am împins 17. 

STEVEN: Noi rămânem 17 pe partea de sus, așa - 

DAVID MALAN: Bine, bine. 

STEVEN: - plasați-l în jos. 

DAVID MALAN: În regulă. Se face ușor. Eu nu am de gând să te ajute de data asta. Împinge 22. 

STEVEN: Done. Devenind o radieră. Am devenit o perie. Și apoi eu sunt punerea 22. 

DAVID MALAN: 22. Excelent. Deci, o mai mult timp. Acum voi să împingă pe stiva 26. 

STEVEN: Ooh. Oh, Doamne. M-ai prins cu garda jos. 

DAVID MALAN: Nu ai vezi vine asta? 

STEVEN: Nu am văzut asta venind. Am putea capacitate de re-inițială? 

DAVID MALAN: Asta este o întrebare bună. Așa că am un fel de noi vopsite într-un colț aici. Există într-adevăr nu este de bun pentru Steven pentru că am alocat această matrice static, ca să spunem așa, în interiorul din structura de date. Și am codat esență tare aceasta să fie de mărime trei. Deci nu se poate realoca adevărat. 

Am putea, dacă ne-am întors în, am redefinit tăvi pentru a fi un indicator care vom folosi apoi malloc în memoria mână la. Pentru că dacă ne-am memoria din heap prin malloc, am atunci s-ar putea elibera. Dar, înainte de eliberând-o, am putea realoca o bucată mai mare de memorie, actualiza indicatorul, și așa mai departe. Dar pentru acum, acest lucru este într-adevăr tot ce putem face. Apăsați și pop sunt probabil vor să aibă de a semnala o eroare. 

Deci, de exemplu, implementarea nostru de impuls ar putea reveni un bool care a revenit anterior adevărat, adevărat, adevărat. Dar a patra oară, se va avea pentru a reveni fals, de exemplu. Bine. Foarte bine facut. Felicitări. Ai câștigat mingea de stres azi. 

[Aplauze] 

STEVEN: Mulțumesc. 

DAVID MALAN: Mulțumesc. OK, deci acest lucru nu pare a fi mult de un pas înainte, nu? Am descris această structură de date. A fost convingătoare, corect? Sisteme de operare place. Aparent web poate face uz de acest lucru, și alte aplicații încă. Dar ceea ce o limitare prost că suntem înapoi la fel de săptămână două limite unde ne-am fixat tablouri dimensiuni. 

Deci, există într-adevăr un cuplu de metode am putea rezolva aceasta. Am putea aloca dinamic matrice, Nu de greu de codificare ca am făcut aici, dar în loc să re-declararea acest lucru, doar pentru a fi clar, ca ceva de genul asta. Int * tăvi nu, decide pe o capacitate încă. Dar când am declara stivă în altă parte în codul meu, am putea numi apoi malloc, obține adresa de o bucată de memorie, și am putea atribui că adresa de tăvi. 

Și apoi, pentru că este doar o bucată de memorie, aș putea continua să utilizeze pătrat notație suport în mod obișnuit. Pentru că din nou, nu e un fel de acest echivalentul funcțional de matrice și bucăți de memorie care vin înapoi la malloc. Putem trata unul ca celălalt folosind aritmetica indicatorul sau notație suportul pătrat. Astfel că este o singură abordare. 

Dar cum altfel am putea să pună în aplicare această aceeași structură de date, eventual? Dreapta? Mă simt ca și cum tocmai am rezolvat această problema ca acum o săptămână. Care a fost soluția la această problemă că Steven a fugit în? Listele astfel legate, chiar. 

În cazul în care problema este că suntem pictura ne într-un colț de alocarea în avans, prea puțină memorie pe care le apoi de-a face într-un fel de, ei bine, de ce nu evita doar că emite cu totul? De ce nu declara doar tăvi pentru a fi un pointer la un nod, Ergo o lista inlantuita, și apoi pur și simplu aloca noduri noi de fiecare dată Steven necesar pentru a se potrivi o Numărul în structura de date. 

Deci, imaginea ar trebui să se schimbe. Nu va fi la fel de curat ca și simplu ca doar o serie de trei int. Acum o să fie un pointer la o struct, și că struct se va au un int și un pointer viitoare. Se va conduce prin care indicatorul la altul astfel struct să un alt astfel de struct. Deci, imaginea ar fi de fapt obține un Messier pic. Și ne-ar fi săgeți legarea totul împreună. 

Dar asta e bine, nu, pentru că am văzut cum să facă acest lucru. Și odată ce te confortabil implementarea ceva ca un legat Lista, care va trebui să faceți dacă aveți alege să pună în aplicare un tabel hash cu înlănțuirea separată pentru p-set 6, puteți să-l utilizați ca un bloc, sau un ingredient, sau în Scratch vorbesc, o Procedura, ceva ce ai pus, ai a creat propria piesa de puzzle pe care le puteți apoi reutilizarea. Compromisuri lucru, dar eventualele soluții pe care le-am văzut de fapt înainte. 

Deci, destul de des, veți vedea acest lucru în fiecare an sau doi când Apple lanseaza ceva nou, și toți oameni nebuni linie in afara de Apple magazin să cumpere marginal lor upgrade de pe hardware. Spun acest lucru, e OK, pentru că Eu sunt unul dintre acei oameni. Deci, ce fel de structuri de date s-ar putea reprezenta această realitate? 

Ei bine, haideți să o coadă, o linie de apel. Deci britanic ar numi ea de obicei o coadă oricum, asa ca este un nume frumos. Și cele două operații pe care o coadă sprijină vom numi un Puneți în coadă funcționare și o operație dequeue, care sunt similare în spirit pentru a împinge și pop. E doar un fel de diferit în convenție, ceea ce ne cheamă acestea. Dar a Puneți în coadă ceva înseamnă a adăuga sau se introduce la structura de date. Pentru a dequeue înseamnă să-l scoate. Dar întrucât o stivă a fost un date LIFO structura, o coadă este o premieră în, în primul rând în structura de date. 

Daca esti prima persoana din linie, va fi prima persoană pentru a obține de linie și cumpere noul dispozitiv. Imaginați-vă cât de supărat ar fi acești oameni daca Apple folosit în loc o stivă, pentru exemplu, pentru punerea în aplicare a cules din noua jucărie. Deci, cozile sens, cu siguranță, și ne putem gândi la tot felul de aplicații, probabil, pentru cozile, mai ales atunci când doriți corectitudine. Deci, cum am putea pune în aplicare aceste ca o structură de date? 

Ei bine, eu propun ca am putea Trebuie să facem în acest fel. Așa că am de gând să aibă acum numere. Deci, vom păstrați-l simplu și nu vorbesc în mod necesar din punct de vedere tăvi. Doar numerele care oamenii de ajuns. Capacitatea este de gând să, din nou, fixa numărul total de persoane care pot fi în această linie, ca de trei sau orice altă valoare. 

Dar eu propun ca am nevoie pentru a ține evidența nu numai de mărimea coadă, cât de multe lucruri sunt în ea. Deci dimensiunea este curent mărime, capacitate este dimensiunea maximă. Doar din nou, nomenclatura prin convenție. De ce am nevoie de un int suplimentare de interior de o coadă pentru a urmări care este în partea din față a liniei? De ce am nevoie pentru a face acest lucru, în acest caz? 

Ei bine, ce este această imagine va schimba? Probabil că pot reutiliza mai de această imagine. Lasă-mă să merg mai departe și șterge ce e aici. Vom da acest lucru un ușor nume diferit aici. Să scăpăm de 17, să scăpăm din 9, să scăpăm de 3. Și haideți să adăugați un alt lucru. Eu propun ca am nevoie pentru a ține evidența frontală a listei, care este doar va fi un int la fel de bine. Și am de gând să-l păstrați simplu. Nici o lista inlantuita de acum. 

Vom admite că vom ciocni de această limită. Dar ceea ce vreau să văd întâmplat de data asta? Așa că aș merge mai departe și primul persoană vine în linie, și e numărul 9. Avem bile de stres. Pot să fure, să zicem, două sau trei persoane? Unu, doi, trei? Hai sus. Chiar din fata, deoarece vom face asta rapid. 

Fiecare dintre voi este acum de gând să fie un băiat ventilator în linie de la Apple. Tu nu va primi hardware-ul Apple la sfârșitul acestui totuși. Bine. Deci, tu ești numărul 9, tu esti numărul 17, numărul 22. Acestea sunt numere arbitrare, cum ar fi carduri de student sau fleacuri. Și într-o clipă, să începem pentru a începe adăugarea de lucruri. Și voi alerga la bord aici de data asta. 

Deci, în acest caz, am inițializat față de a fi - Eu de fapt, nu-mi pasă cu adevărat ceea ce față este, deoarece dimensiunea este zero. Deci, acest lucru s-ar putea la fel de bine doar fi un semn de întrebare. Acestea sunt toate semne de întrebare. Deci, acum vom începe pentru a vedea de fapt, unele oameni garnitură de până la magazin. 

Deci, în cazul în care numărul 9, tu ești primul acolo la 5 AM, mergeți mai departe și linia de sus, sau cu o noapte înainte. OK. Deci, acum 9 este aici. Deci 9 este în fața listă. Așa că am de gând să merg mai departe și să actualizeze dimensiunea acestor date actuale Structura sa nu fie 0 mai, ci să fie 1. Am de gând să pună 9 la fata de lista. Lasă-mă să merg mai departe și comuta pe ecran astfel încât să putem vedea trecutul ne aici. 

Și acum ce vreau pentru a pune în față? Voi urmări ca fata de coada chiar acum este la locația 0. Pentru că ceea ce se viitoare va întâmpla? Ei bine, să presupunem că acum am Puneți în coadă 17, de asemenea. Trăiește în linie acolo. Și din nou, un fel de ușă la Magazinul va fi aici. Așa că acum am adăugat 17. Și, chiar dacă acești oameni sunt blocarea ecran, care e OK, pentru că putem vedea aici. Scuze. 

Audiența: Ne putem muta - 

DAVID MALAN: Nu, e în regulă. Este foarte mare acolo. Deci, 17 este acum în interiorul cozii. Am nevoie de a actualiza care câmpurile acum, deși? OK, cu siguranta dimensiune. Și cum despre fata? OK, nu. Față nu trebuie să se schimbe, deoarece spre deosebire de o stivă, am doresc să mențină corectitudine. Deci, dacă 9 a venit în primul rând, dorim 9 să fie primul din linia și în magazin. 

De fapt, să vedem asta. Înainte de a introduce 22, să mergeți mai departe și dequeue 9. Care e numele tău din nou? 

Audiența: Jake. 

DAVID MALAN: Jake se întâmplă să fie dequeued acum. Astfel încât să obțineți pentru a merge în magazin. Și pretinde că magazinul este acolo. Deci, acum ce are nevoie - dit-dit-dit! Ce trebuie să se întâmple acum? Decizie de design. Deci, nu un instinct rău, dar - Care e numele tău din nou? 

Audiența: David. 

DAVID MALAN: David. Deci, ce a făcut David? El a fost încercarea de a sorta a stabili datelor Structura și pentru a muta de la locația lui în fosta locație a lui Jake. Și asta e bine, dacă suntem dispuși să considere că aceasta este o detalii de implementare. Dar, mai întâi, să actualizeze datele Structura înainte de a face acest lucru. Pentru că nu-mi place ideea de toate oamenii deplasare în această linie. 

Nu e mare lucru dacă David o face cu un singur pas, dar, din nou, cred că înapoi la când am avut opt ​​voluntari de pe scenă și am făcut ca inserare fel, în cazul în care am avut de a începe mișcare toată lumea din jurul. Care a primit scump, nu? Asta mă face să mă piti despre Big O de n, O mare de n pătrat din nou. Nu se simte ca un rezultat ideal. 

Așa că haideți să actualizeze doar acest lucru. Astfel încât dimensiunea cozii nu mai este 2. Acum e pur și simplu 1. Dar pot actualiza acum ceva N-au actualizat înainte, fata de lista. Am putea spune doar, este că locația 1? Deci, acum avem valoare gunoi aici, Valoarea gunoi aici, și David în mijlocul de acest gunoi. Dar structura de date este încă intactă. 

Și, de fapt, nici măcar nu trebuie să schimba fostul numărul lui Jake 9, pentru care îi pasă. Am suficiente informații acum în Dimensiunea că știu că sunt o persoană în această coadă. Și știu că acea persoană este la locația 1, nu 0. Eu nu contez. Deci 1, de asemenea. Deci, structura de date este încă OK. 

Ei bine, ce se întâmplă în continuare? Să Puneți în coadă - Care e numele tău? 

Audiența: Callen. 

DAVID MALAN: Callen. Să Puneți în coadă un Callen, și 22 este acum în coada de așteptare. Deci, acum ce trebuie să se schimbe aici? Fata nu este de gând să schimba, evident. Dimensiunea se va schimba pentru a fi din nou 2. 22 și se termină aici, 9 este încă prezent, dar este în mod efectiv o Valoarea gunoi acum. E doar o rămășiță de Jake trecut. 

Deci, acum, ce se întâmplă dacă Am dequeue David? O ultimă operație, dequeue David. Am putea schimba, dar eu propun Să face ca munca mai puțin posibil. Acum, structura mea de date se înapoi în mărime de la 2 la 1. Dar partea din fata a cozii acum devine 2. Nu am nevoie pentru a schimba aceste numere doar încă, pentru că sunt doar valorile de gunoi. 

Dar acum ce se întâmplă? Să presupunem că m-am Puneți în coadă, 26? Mă simt ca și cum mi-e locul aici. Deci, eu sunt enqueued. Asa ca am un fel de locul aici. Și, chiar dacă nu prea Apreciez acest lucru vizual pe scena, pentru că avem o mulțime de cameră, că ar trebui nu sta aici, de ce? 

Audiența: Ești în afara limitelor. 

DAVID MALAN: Corect. Sunt în afara limitelor. Am indexate dincolo de limitele acestei matrice. Am într-adevăr ar trebui să fie într-una din trei locatii posibile. Acum, unde e cel mai natural de a merge? Propun să leveraged o săptămână, un truc. Operatorul mod, procentual. Pentru că eu sunt punct de vedere tehnic în picioare la locație 3, dar eu 3 capacitate MOD, deci 3, un semn procent, 3 - Capacitatea este 3. Ce-i asta? Care este restul atunci când vă împărțiți 3 de 3? 0. 

Astfel că mă pune fost Jake a fost, care este, de fapt bine. Deci, acum punerii în aplicare de acest lucru se va fi un pic de o durere de cap. Este într-adevăr doar o singură linie de dureri de cap, de cod. Dar cel puțin acum nu e gunoi valoare aici, dar există două int legitime aici. Și eu susțin că acum am făcut exact ceea ce trebuie să facem, atât timp cât vom schimba ceea ce Jake valoare a fost să fie 26. 

Acum avem suficiente informații încă pentru a menține integritatea acestei structuri de date. Suntem încă un fel de noroc atunci când am doriți să inserați total de patru sau mai multe elemente, dar eu pot cel puțin să destul de utilizarea eficientă a acestei constante timp, de fapt. Nu trebuie să vă faceți griji cu privire la schimbarea toată lumea, ca înclinația lui David a fost. 

Orice întrebări cu privire la stive, sau acest coadă? 

Audiența: Este motivul aveți nevoie de mărime, astfel încât să știți în cazul în care să aibă o persoană? 

DAVID MALAN: Exact. Am nevoie să știu dimensiunea de matrice pentru că am nevoie să știu exact cum multe dintre aceste valori sunt legitime, și astfel încât să pot găsi în cazul în care pentru a pune Următoarea persoană. Exact. Dimensiunea este de - de fapt, nu am actualiza acest încă. M-am adăugat la 26. Dimensiunea este acum, nu 1, ci 2. Deci, acum acest lucru într-adevăr ajută-mă să găsesc cap de listă, care nu este 0, nu 1, dar este 2. Partea din față a listei este într-adevăr numărul 22. Pentru că a venit în primul rând, așa că ar trebui să fi permisă în magazin înainte de mine, chiar dacă vizual stau mai aproape de magazin. 

În regulă? O rundă de aplauze pentru aceste baieti și le vom lăsa să iasă de acolo. 

[Aplauze] 

DAVID MALAN: aș putea să vă păstrați tava. Am putea vedea ce se întâmplă dacă vrei, dar poate că nu. Bine. Deci, ce facem acum noi ce facem? Ei bine, permiteți-mi să propun că există o alte câteva structuri de date am putea începe adăugarea la setul nostru instrument care va de fapt este destul, destul de relevant vom arunca cu capul în chestii web. Care din nou, are un fel de conexiune la copaci în formă de ceva numit DOM, documentul modelul de obiect. Dar vom vedea mai mult de că înainte de mult timp. 

Permiteți-mi să propun definitionally pe care le apel copac acum ceea ce s-ar putea, stiu ca mai mult de un arbore genealogic, în cazul în care au unele strămoș la rădăcinile copacului. Un matriarhatului patriarhal sau o la foarte de sus a copac. Fără partenerul de viață, în acest caz. Dar acum avem ceea ce vom numi copii, care sunt noduri care atârnă pe copil la stânga sau la dreapta copil, săgeți cum este descris aici. 

Cu alte cuvinte, într-o structură de date arbore în calculator, un copac are zero sau mai multe noduri. Dacă prezintă cel puțin un nod, care se numește rădăcină. Sunt lucruri pe care vizual ne trage în sus. Și că nod, la fel ca orice alt nod, poate au zero, unu, sau doi, sau trei, sau oricât de mulți copii Structura de date acceptă. În acest caz, rădăcină, stocarea valoarea unul, are doi copii, 2 și 3, așa că, în general, numim 2 stângă copil și 3 copilul dreapta. 

Și atunci când vom ajunge până la 5, 6, și 7, 6 ar putea fi numit copilul mijlociu. Dacă aveți patru copii, devine confuz. Deci, noi nu mai utilizați acest tip de comenzi rapide verbal. Dar este într-adevăr doar un arbore genealogic. Și frunzele aici sunt nodurile care ei nu au copii. Ei stau pe partea de jos a arborelui. 

Deci, cum am putea implementa un copac care are doar doi copii la maxim? Vom un arbore binar apel. Bi nou adică două, în acest caz, ca și cu binar. Și astfel se poate avea zero, unu, sau doi copii la maximum. 

O să propun ca vom pune în aplicare nodul pentru ca structură cu un n int, și apoi doi pointeri, unul numit a plecat, unul numit dreptate. Dar acestea sunt doar frumos convențiile arbitrare. Și ceea ce e frumos acum, mai ales dacă fel de luptat cu conceptual recursivitate, sau a crezut că nu era într-adevăr o soluție la nimic, mai ales dacă ai putea a alerga afară de memorie. Acum, că vorbim despre date Structuri si algoritmi care permit ne să traverseze și să le manipuleze, se dovedește că recursivitate se întoarce în o mult mai convingatoare dacă nu mod frumos. 

Deci, acest propun este aplicarea de o funcție de căutare. Având în vedere cele două intrări - deci cred că de acest lucru ca o cutie neagră. Având în vedere cele două intrări, n, int, și o pointer la un copac, un pointer la o nod, sau chiar la rădăcina unui copac, am susțin că această funcție poate returna adevărat sau fals, că valoarea n Este în interiorul acestui copac. 

Ce este în interiorul acestui cutie neagră? Ei bine, patru filiale. Primul doar verifică. Dacă copac este nul, doar întoarce false. Dacă nu există nod, nu exista nici n, nu există nici un număr, doar întoarce false. Dacă totuși, n, valoarea pe care o căutați pentru, este mai mică de copac săgeata n, și doar pentru a fi clar, ce înseamnă când Scriu copac și apoi săgeata notație, n? Exact. Aceasta înseamnă că dereference indicatorul numit copac. Du-te acolo, iar apoi obține în interiorul de care nodul și să obțină domeniul său numit n. Și apoi comparați n real, care a fost a trecut în căutare de ea. 

Deci, dacă n este mai mic, valoarea n în nodul copac în sine, ei bine, Ce înseamnă asta? Asta nu înseamnă nimic la prima vedere. Dreapta? La fel ca atunci când aveți o serie de valori, ar putea dori să se aplice binar căuta ca o formă de divizare și cuceri. Dar ceea ce presupunere am nevoie pentru a face pentru binar de căutare pentru a lucra la toate în cartea de telefon și exemplele anterioare? 

Cum să fie sortate. Deci, haideți să rafineze definiția de copac aici nu sa fie doar un copac, care poate avea orice număr de copii. Nu doar un arbore binar, care poate avea 0, 1, 2 sau maxim. Ci ca un arbore binar de căutare, sau BST, care este doar un mod fantezist de a spune o arbore binar astfel încât fiecare nod copil stânga, dacă este prezent, este mai puțin de nod. Și dreptul copilului la fiecare nod, dacă este prezent, este mai mare decât nodul în sine. 

Deci, cu alte cuvinte, dacă ar fi să atragă out copac, toate numerele sunt echilibrat cu grijă ca acest lucru, astfel încât, dacă aveți 55 ca rădăcină, 33 poate merge la stânga ei, pentru că este mai puțin de 55. 77 pot merge la dreapta sa, deoarece este mai mare de 55. Dar acum observa, aceeași definiție, este o definiție recursivă verbal, trebuie să se aplice pentru 33. Copilului stânga 33 trebuie să fie mai mică decât aceasta, și dreptul copilului de 33, 44, trebuie să fie mai mare decât aceasta. 

Deci, acesta este un arbore binar de căutare, și Eu propun, folosind un pic de recursivitate, putem găsi acum n. Deci, dacă n este mai mic decât valoarea n care este nodul curent, am de gând să merg înainte și punt, ca să spunem așa, și doar reveni indiferent de răspunsul este de căutarea n pe copilului stânga copac. Observați din nou, această funcție doar se așteaptă la o stea nod, un pointer la un nod. Deci, cu siguranță, eu pot face doar copac săgeată la stânga, ceea ce va conduce ma la un alt nod. Dar ceea ce este că nodul? 

Ei bine, în conformitate cu această declarație, stânga este doar un pointer, astfel încât doar înseamnă Trec la funcția de căutare un pointer diferit, și anume cel care reprezintă copac copilul meu stâng a lui. Deci, în acest caz, indicatorul la 33, dacă acesta este introdus de nostru eșantion Între timp, în cazul în care n este mai mare decât valoarea n la nodul curent din arbore, atunci eu sunt merge mai departe și punt în celălalt direcție și spun, eu nu fac știu dacă această valoare n este în copac, dar știu că dacă este, e în jos meu ramura dreapta, ca să spunem așa. Deci, lasă-mă apel recursiv căutare, care trece un n din nou, dar care trece într-o pointer la copilul meu drept. 

Cu alte cuvinte, dacă sunt în prezent la 55 și eu sunt în căutarea de 99, eu știu că 99 este mai mare de 55, asa ca am rupt de săptămâni cartea de telefon în urmă și am a mers bine, la fel suntem merge chiar aici. Și nu știu dacă e la dreapta mea copil, și nu este, 77 este acolo, dar Știu că e în acea direcție. Deci, eu numesc căutare pe copilul meu drept, 77, și să figura căutare de la există în cazul în care 99 în această arbitrară exemplu este de fapt acolo. 

Altfel, ceea ce este cazul finale? Dacă pomul este nul este un caz. Dacă n este mai mic nodul curent Valoarea este un alt caz. Dacă n este mai mare decât curentul Valoarea nodului este un al treilea caz. Care este a patra și ultima situație? Cred că suntem de cazuri, nu? Trebuie să fie că n este în nodul curent, care sunt pe. 

Deci, dacă eu sunt în căutarea pentru 55 la acest punct în poveste, ca ramură a copac se va întoarce adevărat. Deci, ce e interesant aici este că noi De fapt, spre deosebire de ultimele săptămâni, ne-am cam a avea două cauze de bază. Și ei nu trebuie să fie în partea de sus. În partea de sus este un caz de bază, deoarece în cazul în care copac este nul, nu e nimic de făcut. Doar întoarce o codat greu Valoarea de fals. 

Ramura de jos este un fel de implicit, prin care dacă le-am verificat pentru null, am verificat dacă ar trebui să fie a plecat, dar nu ar trebui să fie, ne-am verificat dacă acesta ar trebui să fie corect, dar nu ar trebui să fie, în mod clar trebuie să fie chiar unde suntem. Asta e un caz de bază. Deci, există două cazuri recursive sandwich în mijloc. Dar am fi putut scrie aceasta, în orice ordine. M-am gândit că un fel de simtit naturale pentru a verifica în primul rând pentru o posibilă eroare, apoi verificați stânga, apoi verificați dreapta, apoi Presupun că sunteți la nodul sunteți de fapt cautati. 

Deci, de ce ar fi acest lucru util? Deci, se dovedește - și lasă-mă să sari la un teaser aici, că e în web. Vom începe să utilizați nu o limbaj de programare la început, dar o limbaj de marcare. Un limbaj de marcare fiind unul care este similară în spirit de programare limba, dar nu vă dau capacitatea de a te exprima în mod logic. Este doar vă oferă posibilitatea de a te exprimi structural. 

În cazul în care vrei să pui ceva pe pagina, pagina de web? Ce culoare vrei să-l facă? Ce dimensiunea fontului vrei să-l facă? Ce cuvinte vă faceți de fapt doresc de pe pagina de web? Deci, asta e un limbaj de marcare. Dar atunci vom prezenta foarte repede JavaScript, care este un cu drepturi depline limbaj de programare. Foarte asemănătoare sintactic în aparență la C, dar va avea unele frumos, mai puternic, mai caracteristici ușor de utilizat. 

Și unul dintre frustrările în acest punct în semestrul este că vom implementa în curând pronuntie în mult mai puține de linii de cod care utilizează alte limbi decât C se permite, dar pentru motive de vom înțelege curând. Aceasta va fi prima pagina web, cum ar. Acesta va fi complet underwhelming, primul facem. Acesta va spune pur și simplu, salut lume. Dar dacă nu ați mai văzut-o înainte, aceasta este HTML, Hypertext Markup Language. 

Dacă te duci la o anumită opțiune de meniu în cele mai multe orice browser, de pe orice pagina web pe pe internet, puteți vedea HTML că unii oameni au scris la crea acea pagină web. Și, probabil, nu arata la fel scurt sau elegant ca acest lucru. Dar va urma modelul de acestea paranteze deschise și slash și litere și numere potențial. 

M-am gândit să vă dau un teaser de ceea ce veți fi în stare să facă după luarea CS50. Lasă-mă să merg la cs.harvard.edu / Rob, pagina noastră Rob Bowden. El a făcut acest lucru pentru noi. Astfel încât veți fi în curând posibilitatea de a face acest lucru. Și, de asemenea, ceea ce ai auzit în această dimineață - ceea ce ai auzit în această dimineață - 

[HAMSTER Dance Music] 

- Vei fi în măsură să facă acest lucru. Care ne așteaptă miercuri. Ne veți vedea atunci. 

[HAMSTER Dance Music] DAVID MALAN: La următoarea CS50 -