SPEAKER 1: Bine, deci acest lucru este CS50 Acesta este sfârșitul săptămânii cinci. Și reamintească faptul că ultima dată am a inceput sa caute la datele crescator structuri care au început să rezolve probleme, care au început să introducă noi probleme, dar cheia pentru acest era genul de filetare pe care le a început să facă de la nod la nod. Deci, aceasta este, desigur, o listă individual legat. Și de individual legate, Adică nu e doar o fir între fiecare dintre aceste noduri. Se pare că poți să faci crescator lucruri cum ar fi liste de două ori legate prin care aveți o săgeată merge în ambele direcții, care poate ajuta cu anumite eficiență. Dar acest lucru a rezolvat problema? Ce problemă a rezolva acest lucru? De ce a ne pasa de luni? De ce, în teorie, am grijă de luni? Ce face? 

Audiența: putem redimensiona dinamic. 

SPEAKER 1: OK, astfel încât să putem dinamic al redimensiona. Bine făcut amândoi. Astfel încât să puteți redimensiona dinamic această structură de date, în timp ce o matrice, Reamintim, trebuie să știi un priori cât de mult spațiu pe care doriți Și dacă ai nevoie de un pic mai mult spațiu, ești un fel de noroc. Trebuie să creați o gamă cu totul nou. Trebuie să muta toate dvs. date de la unul la altul, în cele din urmă a elibera matrice vechi dacă poți, și apoi continua. Care tocmai se simte foarte costisitoare și foarte ineficiente, și într-adevăr poate fi. Dar aceasta nu este totul bine. Plătim un preț, ceea ce a fost un prețurilor mai evidente ne plata prin utilizarea unei liste legat? 

Audiența: Trebuie să utilizați spațiu dublu pentru fiecare dintre ele. SPEAKER 1: Da, asa ca avem nevoie cel puțin de două ori mai mult spațiu. De fapt, am realizat această imagine a lui chiar un pic înșelătoare, deoarece pe IDE CS50 într-o mulțime de moderne computere, un pointer sau o adresă nu este de fapt patru octeți. Este foarte des acestea zile opt bytes, care înseamnă partea de jos mai dreptunghiuri acolo în realitate sunt un fel de două ori mai de mare ca ceea ce am desenat, ceea ce înseamnă că utilizați de trei ori mai mult spatiu ca am putea fi altfel. Acum, în același timp, suntem încă mai vorbesc bytes, nu? Noi nu neapărat vorbesc megabytes sau gigabytes, cu excepția cazului în aceste structuri de date ajunge mare. 

Și așa astăzi vom începe să ia în considerare cum am putea explora date mai eficient dacă în De fapt, datele devine mai mare. Dar să încercăm să canonic operațiunile primele pe care le puteți face pe acestea tipuri de structuri de date. Deci, ceva ca o legătură Lista sprijină, în general, operațiuni place ștergeți, insera, si cauta. Și ce vreau să spun cu asta? Asta înseamnă doar că, de obicei,, dacă oamenii sunt utilizați lista legate, ei sau altcineva a pus în aplicare funcții cum ar fi Ștergere, Inserare, și de căutare, astfel încât să puteți face de fapt ceva utile cu structura de date. Deci, haideți să aruncăm o privire rapidă la cum am putea pune în aplicare unele cod pentru o listă legată, după cum urmează. 

Deci, aceasta este doar un cod C, nici măcar un program complet că eu chiar repede incitat. Nu e online în distribuția cod, pentru că nu va rula de fapt. Dar observați Am doar cu un comentariu a spus, dot dot dot, e ceva acolo, dot dot dot, ceva acolo. Și să uita doar la ce piesele suculente sunt. Deci, pe linia trei, reamintească faptul că acest lucru este acum Am propus declararea un nod trecut timp, una dintre aceste obiecte dreptunghiulare. Acesta are o int care vom suna N, dar am putea numi orice, și apoi o stea nod struct numit următor. Și doar pentru a fi clar, că de-al doilea linie, pe linia șase, ce e asta? Ce o face pentru noi? Pentru că cu siguranță pare mai criptic decât variabilele noastre obișnuite. 

Audiența: Se face muta peste o. 

SPEAKER 1: Se face muta peste o. Și pentru a fi mai precis, se va stoca adresa de nodul care este menit să fie semantic lângă el, nu? Deci, nu va muta neapărat ceva. E doar de gând să stoca o valoare, care este O să fie adresa de un alt nod, și de aceea am spus struct stele nod, steaua denotă un pointer sau o adresă. OK, deci acum, dacă presupunem că avem acest N disponibile pentru noi, și să presupunem că cineva are altcineva introdus o grămadă de numere întregi într-o listă legată. Și această listă este legată indicat de un punct o variabilă numită listă care este a trecut pe aici ca un parametru, cum pot face despre line 14 de punere în aplicare de căutare? Cu alte cuvinte, dacă am de punere în aplicare Funcția a cărui scop în viață este de a lua un întreg și apoi începutul unei liste legate, că este un pointer la lista legat. Ca și în primul rând, care a cred David a fost voluntar la data de Monday, el a fost îndreptat la tot legat listă, e ca și cum ne trece David în ca argument aici. Cum vom merge despre care traversează această listă? Ei bine, se pare că, deși indicii sunt relativ noi acum pentru noi, putem face acest lucru relativ direct. 

Am de gând să merg mai departe și declara o variabilă temporară care prin convenție este doar de gând să fie numit pointer, sau PTR, dar ai putea numi tot ce vrei. Și am de gând pentru a inițializa l la începutul listei. Astfel încât să puteți fel de a gândi această ca si mine profesorul de altă zi, un fel de îndreptat pe cineva printre oameni noastre ca voluntari. Deci, eu sunt o variabilă temporară care este doar arătând spre același lucru că nostru numit coincidență voluntar David a fost, de asemenea, subliniind. Acum în timp ce indicatorul este nu null, deoarece rechemare că nulă este o anumită valoare deosebită Sentinel delimitează sfârșitul listei, Deci, în timp nu am îndreptat la teren ca ultimul nostru voluntar a fost, să mergem mai departe și de a face următoarele. Dacă pointer-- și acum am un fel de vreau să facem ceea ce am făcut cu elevul structure-- dacă pointer punct viitoare equals-- mai degrabă, dacă indicatorul punct N este egal cu este egal cu variabila N, The argument care a fost adoptată în, apoi vreau să merg mai departe și spune return true. Am găsit numărul N interiorul unul dintre nodurile lista mea legate. Dar punctul nu mai lucrează în acest context, pentru că pointer, PTR, este într-adevăr un pointer, o adresă, am de fapt, poate minunat utiliza în cele din urmă o bucată de sintaxă acest tip de mărci simț intuitiv și de fapt utilizați o săgeată aici, ceea ce înseamnă merge de la acea adresă la întreg acolo în. Deci, este foarte similară în spirit operatorului dot, dar pentru că nu pointer este un pointer și nu o struct în sine, vom folosi doar săgeata. 

Deci, în cazul în care nodul curent că Eu, variabilă temporară, am arătând spre nu este N, ceea ce vreau să fac? Ei bine, cu voluntari umani mele că am avut aici de altă zi, dacă prima mea umană nu este cea pe care am doresc, și poate al doilea om nu este cel vreau, iar al treilea, am nevoie pentru a menține în mișcare fizic. Ca și cum pot parcurge o listă? Când am avut o serie de tine, la fel a făcut cum am, plus, plus. Dar în acest caz, este suficient să se face pointer, devine, pointer, alături. Cu alte cuvinte, următorul câmp este ca toate mâinile stânga că voluntarii noastre umane luni au fost utilizați pentru a indica la un alt nod. Acestea au fost următoarele vecinii lor. 

Deci, dacă vreau să-și intensifice prin această listă, Nu pot să fac eu, plus, plus mai, Trebuie în schimb să spun I, pointer, se va la egal indiferent de domeniul următor este, următorul câmp este, următorul câmp este, în urma toate aceste mâini stânga că am avut pe scena de indicare unor valori ulterioare. Și dacă mă prin că întreaga repetare, și în cele din urmă, l-am lovit nul nu au găsit N totuși, doar mă întorc false. Deci, din nou, tot ce facem aici, ca pe imaginea urmă cu o clipă, este incepand de îndreptat de la începutul listei probabil. Și apoi m-am verifica, este valoarea Caut egal la nouă? Dacă este așa, mă întorc adevărat și am terminat. Dacă nu, actualizați mâna mea, AKA pointer, la punctul la locația pe săgeata de lângă, iar apoi locație pe săgeata de lângă, a și următorul. Sunt pur și simplu de mers pe jos am prin această matrice. 

Deci, din nou, cui îi pasă? Ca ceea ce este acest ingredient pentru? Ei bine, amintim că am introdus noțiunea de stivă, care este un abstract de date de tip în măsura în care este nu este un lucru C, nu este un lucru CS50, este o idee abstractă, această idee de stivuire lucruri pe partea de sus a unul pe altul care pot fi implementate în buchete de moduri diferite. Și într-un fel ne-am propus a fost cu o matrice, sau cu o listă legată. Și se pare că canonic, o stivă susține cel puțin două operațiuni. Iar cuvintele Buzz sunt împinge, pentru a împinge ceva pe stiva, ca un nou Tray în sala de mese, sau pop, ceea ce înseamnă pentru a elimina cel mai de sus tava din stivă în mese Hall, iar apoi poate că unele alte operațiuni, de asemenea. Deci, cum am putea defini structura că suntem de asteptare acum o stivă? 

Ei bine, avem toate necesar sintaxă la dispoziția noastră în C. am spus, da-mi o definiție tip de o struct interiorul-o stivă, Am de gând să spun este o matrice, de un grămadă de numere și apoi dimensiunea. Deci, cu alte cuvinte, dacă vreau să pună în aplicare acest lucru în cod, lasă-mă să merg și doar un fel de remiză ce acest spune. Deci, acest lucru este de a spune, da-mi un structură care are o matrice, și nu știu ce calitate este, e pare ceva constant care le-am definit în altă parte, și asta e bine. Dar să presupunem că e doar unul, doi, trei, patru, cinci. Deci capacitatea este de 5. Acest element în interiorul meu Structura va fi numit numere. Și apoi am nevoie de unul alte variabile aparent numit dimensiune care initial am de gând să prevadă este inițializată la zero. Dacă nu e nimic în stivă, dimensiunea este zero, și este valorile de gunoi într-un număr. Nu am nici o idee despre ce e acolo încă. 

Deci, dacă vreau să împingă ceva pe stiva, Presupun că sun funcția împinge, și Eu spun împinge 50, cum ar fi numărul 50, în cazul în care ați propune Am trage in acest tablou? Există cinci răspunsuri diferite posibile. În cazul în care vrei să împingă numărul 50? În cazul în care obiectivul de aici, din nou, sunați la functie push, trece într-un argument 50, unde am pus? Cinci possible-- 20% șanse de ghicitul în mod corect. Da? 

Audiența: extrema dreaptă. 

SPEAKER 1: extrema dreaptă. Există acum o sansa de 25% de ghicitul în mod corect. Deci, care ar fi de fapt bine. Prin convenție, voi spune, cu o serie, în general, ne-ar începe de la stânga, Dar am putea cu siguranță încep de la dreapta. Deci, spoilerul aici ar fi că sunt probabil gând să-l atragă pe stânga, la fel ca într-o gamă normală în cazul în care Am începe să mergi la stânga la dreapta. Dar dacă puteți răsturna aritmetica, bine. Nu este vorba doar convențional. OK, am nevoie pentru a face o mai schimba totuși. Acum, că am împins ceva pe stiva, ce urmează? 

Bine, am să incrementa dimensiunea. Așa că lasă-mă să merg mai departe și doar actualiza acest, care a fost zero. Și în loc acum, am de gând pentru a pune în valoare o. Și acum că aș împinge un alt Numărul de pe stiva, cum ar fi 51. Ei bine, am să fac o mai schimbare, care este de până la dimensiunea două. Și apoi că aș împinge unul mai Numărul de pe stiva ca 61, acum am nevoie pentru a actualiza dimensiunea o mai timp, și pentru a obține valoarea 3 ca dimensiunea. Și acum să presupunem că eu numesc pop. Acum pop, prin convenție, nu ia un argument. Cu un teanc, întreg punct de metafora tăvii este că nu aveți putere de apreciere pentru a du-te că tava, tot ce se poate face este cel mai de sus pop cea de la stiva, doar pentru că. Asta e ceea ce face această structură de date. 

Deci, prin această logică, dacă am spune poziție favorabilă, ceea ce vine de pe? Deci 61. Deci, ce este cu adevărat computerul de gând să faci în memorie? Ce codul meu trebuie să fac? Ce ați propune vom schimba pe ecran? Ce ar trebui să se schimbe? Ne pare rău? Așa că am scăpa de 61. Deci, eu pot face cu siguranta asta. Și pot scăpa de 61. Și apoi ce alte schimbarea trebuie să se întâmple? Dimensiune, probabil trebuie să se întoarcă la două. Și așa că e bine. Dar stai un minut, dimensiune un moment în urmă a fost de trei. Hai să facem o verificare bun-simț rapid. Cum am ști că am a vrut să scape de 61? Pentru ca suntem popping. Și așa că am această a doua dimensiune proprietate. 

Stai puțin, eu sunt gândire înapoi la doua saptamani când am început să vorbim despre tablouri, în cazul în care acest lucru a fost locația de zero, acest lucru a fost o locație, aceasta a fost locație doua, aceasta este locația de trei, patru, Se pare ca relație între dimensiunea și elementul care doresc să eliminați din matrice pare să fie exact ceea ce? Dimensiune minus unul. Și așa așa ca oameni știm 61 este pe primul loc. Cum computerul va ști? Când codul, în cazul în care probabil că vrei sa faci dimensiunea minus unul, așa unul cu trei minus este doi, și că înseamnă vrem să scăpăm de 61. Și atunci putem actualiza într-adevăr dimensiunea astfel încât dimensiunea acum merge de la trei la doar două. Și doar pentru a fi pedant, am de gând să propună am terminat, nu? Tu propus intuitiv corect ar trebui să scape de 61. Dar nu le-am un fel de un fel de scăpat de 61? Am uitat în mod eficient că este de fapt acolo. Și cred că înapoi la PSET4, dacă ați citit articolul despre criminalistica, PDF că am avut voi citi, sau va citi în această săptămână pentru PSET4. Amintiti-va ca aceasta este de fapt germane a ideea de calculator forensics. Ce calculator, în general, nu este doar uita în cazul în care ceva este, dar nu merge în și ca încercați să-l zero afară sau suprascrie aceste biți cu zerouri și cele sau un alt tipar aleatoriu dacă nu te face acest lucru în mod deliberat. Deci, intuitia ta era Bine, să scăpăm de 61. Dar, în realitate, noi nu trebuie să deranjez. Trebuie doar să uităm că e acolo prin schimbarea dimensiunea noastră. 

Acum există o problemă cu acest stack. Dacă am păstra împingându lucruri pe stiva, ceea ce este evident se va întâmpla în doar câteva momente de timp? Vom alerga afară de spațiu. Și ce facem? Suntem un fel de filetat. Această punere în aplicare nu lasa ne redimensiona matrice, deoarece cu ajutorul această sintaxă, dacă cred că înapoi la doua saptamani, odată ce ați declarat de dimensiunea unei matrice, nu am văzut încă în cazul în care un mecanism aveți posibilitatea să modificați dimensiunea tabloului. Și într-adevăr C nu are această caracteristică. Dacă spui da cinci-mi Nths, le numesc numere, asta e tot ce ai de gând să-l. Deci, ce facem acum ca de luni, au abilitatea de a exprima o soluție deși, avem nevoie doar pentru a optimiza definiția stivă noastre nu să fie o matrice greu codificate, dar doar pentru a stoca o adresă. 

Acum, de ce este acest lucru? Acum trebuie doar să fie confortabil cu faptul că atunci când programul meu se execută, Am probabil de gând să trebuie să ceară umane, câte numere vrei să stocați? Deci de intrare trebuie sa vina de undeva. Dar, odată ce știu că numărul, atunci eu pot doar folosi ceea ce funcționează pentru a da mi o bucată de memorie? Eu pot folosi malloc. Și pot să spun orice număr de bytes vreau înapoi pentru aceste Nths. Și tot ce am pentru a stoca în numerele variabilă aici în interiorul acestui struct ar trebui să fie ce? Ce de fapt, merge în Numerele în acest scenariu? Da, un pointer la primul octet de care bucată de memorie, sau mai precis, adresa de prima dintre aceste bytes. Nu contează dacă e un byte sau un miliard de bytes, Am nevoie doar să aibă grijă de prima. Pentru că ceea ce garanții și malloc garanții mele sistem de operare, este că bucată de memorie I obține, va fi contigue. Nu va fi lacune. Deci, dacă am cerut pentru 50 bytes sau 1000 bytes, ei toți vor fi Înapoi la spate în spate. Și atât timp cât îmi amintesc cât de mare, cât de de mult am cerut, tot ce trebuie să știu este primul astfel de adresă. 

Deci, acum avem capacitatea de cod. Deși, o să ne ia mai mult timp pentru a scrie asta, am putea realoca acum că memoria de doar stocarea o adresă diferită acolo dacă ne dorim o mai mare sau chiar o bucată mică de memorie. Deci, aici la un off comerț. Acum ajungem dinamism. Avem încă contiguousness am pretind. Deoarece malloc ne va da o bucată contiguu de memorie. Dar acest lucru va fi o durere în gât pentru noi, programator, pentru a coda de fapt sus. E doar mai mult de lucru. Avem nevoie de cod asemanator cu ceea ce am fost trage în urmă doar un moment. Foarte greu de realizat, dar se adaugă complexitate. Și astfel timp dezvoltator, programator Acum este încă o altă resursă că s-ar putea nevoie pentru a petrece ceva timp pentru a obține noi caracteristici. Și apoi, desigur, există o listă de așteptare. Nu vom intra în acest o în detaliu. Dar e foarte similare în spirit. Aș putea pune în aplicare o coadă, și operațiunile sale corespunzătoare, Puneți în coadă sau dequeue, cum ar fi adăugați sau eliminați, e doar un mod de a spune crescator ea, Puneți în coadă sau dequeue, după cum urmează. M-am pot da doar un struct are din nou un număr de serie, are din nou o dimensiune, dar de ce acum am nevoie de pentru a urmări partea din față a unei cozi? N-am nevoie sa stiu partea din față a stack meu. Ei bine, dacă am din nou pentru o queue-- hai doar greu cod-o ca având ca cinci întregi de aici potențial. Deci, aceasta este zero, unu, doi, trei, patru. Acest lucru va fi numitele numere din nou. Iar acest lucru va fi numit dimensiune. 

De ce este nu suficient de a avea doar dimensiuni? Ei bine, hai să împinge acele numere aceleași pe. Așa că am pushed-- I enqueued, sau împins. Acum voi Puneți în coadă 50, și apoi 51, și apoi 61, iar dot dot dot. Așa că e Puneți în coadă. Am enqueued 50, apoi 51, apoi 61. Și care arată identic Stivă până acum, cu excepția am nevoie pentru a face o schimbare. Am nevoie pentru a actualiza această dimensiune, așa că mă duc de la zero la unu la două-trei acum. Cum pot dequeue? Ce se întâmplă cu dequeue? Cine ar trebui să vină de pe această listă în primul rând dacă este linia de la Apple Store? Deci 50. Deci e un fel de complicat de aceasta data. Întrucât ultima dată când a fost super ușor de a face doar dimensiunea minus unu, Ajung la sfârșitul matrice mea în mod eficient în cazul în care numerele sunt, se elimină 61. Dar eu nu vreau să eliminați 61. Vreau sa iau 50, care a a fost acolo la 05:00 pentru a alinia pentru noul iPhone sau fleacuri. Și așa mai departe pentru a scăpa de 50, am nu se poate face doar asta, nu? Pot trece pe 50. Dar ne-am am spus nu trebuie să fie atât de anal ca să zero afară sau ascunde datele. Putem uita doar unde este. 

Dar dacă aș schimba mărimea mea acum la doi, este această informație suficientă să știe ce se întâmplă în coadă meu? Nu chiar. Cum ar fi dimensiunea mea este de două, dar în cazul în care începe coada, mai ales daca mai am aceste numere aceleași în memorie. 50, 51, 61. Așa că am nevoie să-și amintească acum în cazul în care fata este. Și așa cum am propus la acolo, vom avea doar numit Față Nth, a cărui inițială Valoarea ar fi fost ce? Zero, doar începutul listei. Dar acum, în plus față de decrementare dimensiunea, am incrementa doar partea din față. Acum, aici e altă problemă. Deci, odată ce am continua. Să presupunem acesta este numărul de ca 121, 124, și apoi, la naiba, Sunt din spațiu. Dar stai un minut, nu sunt. Deci, în acest moment, în poveste, presupunem că mărimea este unu, doi, trei, patru, astfel încât presupunem că Dimensiunea este de patru, în față este unul, așa 51 este situat în față. Vreau să pun un alt număr aici, dar, la naiba, eu sunt din spațiu. Dar eu nu sunt foarte, nu? În cazul în care aș putea pune unele valoare suplimentară, cum ar fi 171? Da, aș putea fel doar de du-te înapoi acolo, nu? Și apoi tăiați 50, sau doar suprascrie cu 171. Și dacă vă întrebați de ce numerele noastre a primit atât de aleatoriu, acestea sunt luate în mod obișnuit de calculator Cursuri de stiinta de la Harvard după CS50. Dar asta a fost o optimizare bun, pentru că acum nu mă pierde spațiu. Eu încă mai trebuie să vă amintiți cât de mare acest lucru este totală. E cinci totală. Pentru ca nu vreau începe suprascrierea 51. Așa că acum eu sunt încă de spațiu, astfel încât aceeași problemă ca și înainte. Dar puteți vedea cum acum în codul dvs., probabil Trebuie să scrie un pic mai mult complexitate pentru a face să se întâmple asta. Și, de fapt, ceea ce operatorul în C, probabil, permite faci magic acest circularitatea? Da operatorul modulo, semnul sută. Deci, ce fel de misto despre o coadă, chiar dacă păstrăm tablouri de desen ca aceste linii drepte, cum ar fi, dacă ai un fel de despre această curbare ca în jurul ca un cerc, apoi doar intuitiv un fel de lucrări mental Cred că un pic mai curat. Tu ar trebui să pună în aplicare în continuare care model mental în codul. Deci, nu așa de greu, în cele din urmă, să pună în aplicare, dar noi încă pierde size-- Mai degrabă, capacitatea de a redimensiona, dacă nu vom face acest lucru. 

Trebuie să scăpăm de matrice, ne înlocuiți-l cu un singur indicator, și apoi undeva în codul meu am un apel ce funcționează pentru a crea de fapt matrice numita numere? Malloc, sau unele similare funcția, exact. Orice întrebări cu privire la stive sau cozi. Da? Buna intrebare. Ce modulo ai folosi aici. Deci, în general, atunci când se utilizează mod, v-ar face cu dimensiunea de structură de date întreg. Deci, ceva de genul cinci sau de capacitate, în cazul în care este constant, este, probabil, implicat. Dar a face doar modulo cinci Probabil nu este suficientă, pentru că avem nevoie să știm facem înfășurați în jurul valorii de aici sau aici sau aici. Deci tu ești probabil, de asemenea O să vrea să implice mărimea lucru, sau variabila față, de asemenea. Deci e doar acest relativ expresie aritmetică simplă, dar modulo ar fi ingredientul cheie. 

Deci, film de scurt metraj, dacă vrei. O animație care unele Cei de la o altă universitate pune împreună că am adaptate pentru această discuție. Aceasta implică învățarea Jack fapte despre cozile și statistici. 

FILM: După ce la un moment dat, era un tip pe nume Jack. Cand a venit la a face prieteni, Jack nu a avut un talent. Deci, Jack a mers să vorbească la mai tip popular știa. El sa dus la Lou și a întrebat, ce să fac? Lou a văzut că prietenul său a fost foarte întristat. Ei bine, el a început, doar uite cum te îmbraci. Nu ai haine cu un aspect diferit? Da, a spus Jack. Eu sigur fac. Vino la casa mea și O să le arăt. Așa că au plecat la Jack. Și Jack a arătat Lou caseta unde a păstrat toate tricouri lui, și pantalonii lui, și șosete lui. Lou a spus, văd ai toate hainele într-o grămadă. De ce nu te purta unele altele din cand in cand? 

Jack a spus, bine, atunci când am Scoateți îmbrăcămintea și șosete, Le-am spăla și a pus le departe în caseta. Apoi vine următorul dimineața, și până am hop. Mă duc la cutia și a obține hainele mele pe partea de sus. Lou realizat repede problema cu Jack. El a ținut haine, CD-uri, și cărți în stivă. Când a ajuns pentru ceva de citit sau de a purta, el ar alege cartea de sus sau lenjerie. Apoi, când a fost făcut, el l-ar pune imediat înapoi. Înapoi ar merge, pe partea de sus a stivei. Știu soluția, a declarat un Loud triumfător. Aveți nevoie pentru a învăța să a începe să utilizați o coadă. Lou luat hainele lui Jack și le spânzurat în dulap. Și după ce a golit caseta, el doar aruncat. 

Apoi a spus el, acum Jack, la sfârșitul a doua zi, a pus hainele pe stânga atunci când le-a pus deoparte. Apoi mâine dimineață, atunci când vezi soarele, pentru a primi hainele tale pe dreapta, de la capătul liniei. Nu vezi? a spus Lou. Acesta va fi atât de frumos. Vei purta tot o dată înainte de a purta ceva de două ori. Și cu totul în cozi în dulap și raft lui, Jack a început să se simtă destul de sigur de el. Toate datorită Lou și coada lui minunat. SPEAKER 1: Bine, e adorabil. Deci, ceea ce a fost întâmplă cu adevărat pe sub capota acum? Pe care o avem indicii, pe care le avem malloc, că avem capacitatea de a crea bucăți de memorie pentru noi înșine dinamic. Deci, aceasta este o imagine ne zări doar de altă zi. Nu am locui într-adevăr pe ea, dar această imagine a fost întâmplă sub capota pentru săptămâna acum. Și astfel acest lucru reprezintă, doar un dreptunghi pe care le-am elaborat, memoria computerului. Și poate computerul, sau CS50 ID, are o gigabyte de memorie RAM sau sau doi gigabytes sau patru. Nu contează. Sistemul de operare Windows sau Mac OS sau Linux, permite, în esență, programul să cred că are acces la totalitatea memoria computerului, chiar dacă s-ar putea fi difuzate mai multe programe în același timp. Deci, în realitate, că nu prea funcționează. Dar este un fel de o iluzie dat toate programele. Deci, dacă ați avut două concerte de RAM, acest este modul în care computerul ar putea crede ea. 

Acum coincidenta, unul dintre acestea lucruri, unul dintre aceste segmente de memorie, se numește o stivă. Și într-adevăr orice moment până acum în codul scris pe care le-au numit un Funcția, de exemplu principal. Amintiți-vă că în orice moment Am memoria calculatorului trase lui, Intotdeauna mi-am trage un fel de o jumatate de dreptunghi aici și nu deranjez vorbesc despre ce e mai sus. Pentru că atunci când principal este numit, eu pretind că veți obține acest țeapă de memorie care merge aici. Și dacă principal numit în funcție ca de swap, și de swap merge aici. Și se pare, că e în cazul în care se încheie până. Pe ceva numit un teanc în interiorul memoria computerului. Acum, la sfârșitul zilei, aceasta este doar se adresează. E ca și cum octet de zero, octet unul, octet 2 miliarde. Dar dacă te gândești la asta ca acest obiect dreptunghiular, Tot ce facem în fiecare timp ce numim o funcție este stratificarea o nouă felie de memorie. Ne dăm că funcția o felie de memorie proprie pentru a lucra cu. 

Și amintesc acum că acest lucru este important. Pentru că dacă ne-am ceva de genul de swap și două variabile locale ca A și B și vom schimba aceste valori de la una și două la două și un, amintesc că, atunci când se întoarce de swap, e ca și cum aceasta felie de memorie este doar dus. În realitate, este încă acolo forensically. Și ceva e încă de fapt acolo. Dar conceptual, este ca deși este complet dispărut. Și așa principal nu cunosc nici a operei care a fost făcut în această funcție de swap, cu excepția cazului în de fapt a trecut în cele argumente de pointer sau referință. Acum, soluția fundamentală pentru că problema cu schimb trece lucrurile în prin adresa. Dar se pare, de asemenea, ceea ce este fost întâmplă de mai sus că o parte dreptunghiului tot acest timp este dar nu e mai mult de memorie acolo. Iar atunci când dinamic aloca memorie, fie că este vorba în interiorul getString, care am făcut pentru tine în CS50 bibliotecă, sau dacă voi apel malloc și întrebați sistemul de operare pentru o bucată de memorie, aceasta nu vine din stivă. Ea vine de la un alt loc în memoria computerului că se numește grămadă. Și asta nu e diferit. E același RAM. Este aceeași memorie. E doar RAM care este de până acolo în loc de aici. 

Și ce înseamnă asta? Ei bine, în cazul în care computerul are o cantitate finită de memorie și stiva este în creștere în sus, astfel încât de a vorbi, și grămada, conform la această săgeată, este în creștere în jos. Cu alte cuvinte, fiecare timp te sun malloc, Ești dat o felie de memorie de mai sus, atunci poate un pic mai mic, apoi un pic mai mici, de fiecare dată când suni malloc, heap, e de utilizare, este un fel de creștere, în creștere tot mai aproape de ce? Stiva. Deci, se pare ca acest lucru o idee bună? Adică, în cazul în care nu este foarte clar Ce altceva poți face dacă ai doar au o cantitate finită de memorie. Dar acest lucru este cu siguranță rău. Aceste două săgeți sunt pe o Crash Course unul pentru altul. 

Și se pare că tipul rău, oameni care sunt deosebit de bune, cu programare, și încercarea de a hack în computere, poate exploata această realitate. De fapt, să luăm în considerare un pic fragment. Astfel încât acesta este un exemplu puteți citi despre mai în detaliu pe Wikipedia. Vă vom indica la Articolul dacă curios. Dar există un atac, în general, cunoscut sub numele de buffer overflow care a existat atâta timp cât oamenii au avut capacitatea de a manipula memoria calculatorului, în special în C. Deci, acesta este un program foarte arbitrar, dar să-l citesc de jos în sus. Principal în stele argc char argv. Deci, este un program care ia argumente în linia de comandă. Și tot principal se pare că este de apel o funcție, o numesc F pentru simplitate. Și trece în ce? Argv de unul. Deci, trece in F indiferent cuvântul este faptul că utilizatorul tastat la prompt după Numele programului, la toate. Atât de mult ca Caesar sau Vigenere, care s-ar putea aminti faci cu argv. 

Deci, ce este F? F ia într-un șir ca argument unic, AKA o stea char, același lucru, ca un șir. Și se numește în mod arbitrar bar în acest exemplu. Și apoi char c 12, doar în termeni de nespecialist, ceea ce este char c suport 12 face pentru noi? Ce se face? Alocarea de memorie, în special 12 bytes pentru 12 caractere. Exact. Și apoi ultima linie, se amestecă și copie, nu ați văzut, probabil,. Aceasta este o copie șir Funcția a cărui scop în viață este de a copia al doilea argument în primul său argument, dar numai până la un anumit număr de octeți. Deci al treilea argument spune, cât de multe bytes ar trebui să vă copiați? Lungimea bar, indiferent de utilizatorul tastat. Și conținutul bar, că șir, sunt copiat în memoria arătat la la C. 

Deci, acest lucru pare un fel de stupid, și este. Este un exemplu contrived, dar este reprezentant de o clasă de vectori de atac, un mod de a ataca un program. Totul este în regulă și de bună dacă utilizatorul Tipuri într-un cuvânt care este de 11 de caractere sau mai puține, plus backslash zero. Ce se întâmplă dacă de utilizator tipuri în mai mult de 11 sau 12 sau 20 sau 50 de caractere? Ce e acest program de gând să faci? Vina potențial seg. Merge pentru a copia orbește tot în bar până a lungimii sale, care este literalmente totul în bar, în adresa a subliniat, la C. Dar C a dat preventiv doar ca 12 bytes. Dar nu e nici o verificare suplimentară. Nu e nici cazul în care condițiile. Nu e nici o eroare verifica aici. 

Și așa mai departe ceea ce acest program este de gând să faci este doar orbește copia un lucru la altul. Și așa că, dacă vom trage această ca o imagine, aici e doar o așchie de spațiul de memorie. Deci observați în partea de jos, am au bara variabilă locale. Astfel încât indicatorul care va store-- mai degrabă că argument local, care este merge pentru a stoca bara șir. Și apoi observați doar de mai sus, într-o stivă, pentru că de fiecare dată când cere pentru memorie pe stivă, merge un pic deasupra ei pictural, Notă că avem 12 bytes acolo. Cel din stânga sus este C suport zero și cel din dreapta jos este C suport 11. Asta e doar modul în care calculatoarele gând să-l expune. Deci doar intuitiv, dacă bar are mai mult de 12 de caractere în total, inclusiv backslash la zero, în cazul în care este 12 sau suportul C 12 merge? Sau, mai degrabă în cazul în care este 12 caracter sau caracterul 13-lea, caracterul suta merge să se încheie până în imagine? Peste sau sub? 

Drept, deoarece, chiar dacă stiva în sine crește în sus, odată ce ați pus lucruri în ea, din motive de design, pune memoria de sus în jos. Deci, dacă ai mai mult de 12 bytes, ai de gând să înceapă să suprascrie bar. Acum, că e un bug, dar e nu într-adevăr o afacere mare. Dar este o afacere mare, pentru că există mai multe lucruri se întâmplă în memorie. Deci, iată cum am putea pune salut, să fie clar. Dacă am scris în salut la prompt. Backslash zero, H-E-L-L-O, se încheie în termen de aceste 12 bytes, și suntem foarte în siguranță. Totul este bine. Dar dacă am ceva de tip mai mult, cu potential de e O să se strecoare în bara de spațiu. Dar, mai rău încă, se pare în tot acest timp, chiar dacă nu am vorbit despre ea, stiva este folosit pentru alte lucruri. Nu este vorba doar variabile locale. 

C este un limbaj de nivel foarte scăzut. Și ea un fel de secret folosește stiva, de asemenea, să-și amintească atunci când un Funcția este numit, ceea ce adresa este a funcției anterioare, astfel încât să poată sări înapoi la această funcție. Deci, atunci când solicită principale swap, printre lucrurile împins pe stiva nu sunt swap-uri doar variabile locale, sau argumentele sale, de asemenea, împins în secret pe stiva așa cum este reprezentat de felie roșu aici, este adresa de principal punct de vedere fizic în memoria computerului, astfel încât atunci când se face schimb, calculatorul știe că trebuie să ne întoarcem la principal și să termin de executare funcția principală. Deci acest lucru este periculos acum, deoarece în cazul în care utilizator tipuri în bine mai mult de salut, astfel încât de intrare utilizatorului clobbers sau suprascrie această secțiune roșu, logic cazul în care computerul este doar de gând să-și asume orbește că octeții din care felie roșu sunt adresa la care aceasta ar trebui să se întoarcă, Ce se întâmplă dacă un adversar este destul de inteligent sau suficient de norocos pentru a pune o secvență de octeți acolo care arata ca o adresă, dar este adresa de cod că el sau ea vrea computerul să execute în loc de principal? 

Cu alte cuvinte, dacă Ce utilizator este tastarea la prompt, nu este doar ceva ca inofensive salut, dar este de fapt un cod care este echivalent pentru a șterge toate fișierele acestui utilizator? Sau e-mail parola pentru mine? Sau de a începe de logare lor intrarile de la tastatura, nu? Există o cale, să prevadă astăzi, că acestea ar putea tip în nu doar salut lumea sau numele lor, acestea ar putea, în esență, trece în cod, zerouri și cele, care calculatorul greșeli atât pentru cod și o adresă. Deci, deși oarecum abstract, în cazul în care utilizator tipuri în codul contradictorie suficient că vom generaliza aici ca A. A este atac sau adversari. Lucrurile așa de rău doar. Nu ne pasă de numere sau zerouri sau cele astăzi, astfel să ajungi în suprascrierea secțiunea roșu, observați că secvența de octeți. O 835 C la zero la opt la zero. Și acum, ca articol Wikipedia aici a propus, dacă acum, de fapt începe etichetarea bytes din a computerului memorie, ceea ce articol Wikipedia este propunerea este că, ceea ce în cazul în care adresa de care byte stânga sus este de 80 C 0 3508. 

Cu alte cuvinte, în cazul în care personajul negativ este destul de inteligent cu codul său pentru a pune de fapt, un număr de aici care corespunde cu adresa codului el sau ea injectat în computer, ai poate pacali calculatorul în a face ceva. Scoaterea fișiere, email-uri lucruri, sniffing trafic, literalmente ceva ar putea fi injectat în calculator. Și așa un buffer overflow atac în centrul său este doar un prost, prost major al unui tablou care nu avea limitele sale verificate. Și aceasta este ceea ce este super periculos și în același timp foarte puternic în C este că avem într-adevăr accesul la oriunde în memorie. Depinde de noi, programatori, care scrie codul original pentru a verifica durata darn orice matrice care suntem manipularea. Deci, să fie clar, care e fix? Dacă ne reveniți la acest cod, eu nu ar trebui doar schimba lungimea bar, ceea ce altceva ar trebui să mă verificarea? Ce altceva ar trebui să fac pentru a fi preveni acest atac în întregime? Nu vreau să spun doar orbește că ar trebui să copiați cât mai multe bytes cum este lungimea de bare. Vreau să spun, copie ca multe bytes ca sunt in bar până la alocat memorie, sau 12 maxim. Așa că am nevoie de un fel de stare, dacă care face verifica durata de bar, dar dacă depășește 12, am cod doar greu 12 ca distanța maximă posibilă. În caz contrar, așa-numitul tamponul atac preaplin se poate întâmpla. În partea de jos a acestor diapozitive, Daca esti curios pentru a citi mai mult este articolul original real dacă doriți să aruncăm o privire. 

Dar acum, între prețurile plătit aici a fost ineficiențe. Astfel că a fost o rapid nivel scăzut privire la ceea ce Probleme pot apărea acum că ne să aibă acces la memoria calculatorului. Dar am o altă problemă deja dat pe luni a fost doar ineficiența de o listă de legate. Ne-am întors în timp liniar. Noi nu mai avem o gamă contiguă. Nu avem acces aleator. Nu putem folosi notația suport pătrat. Noi pur și simplu trebuie să utilizeze o buclă în timp ce ca cea pe care am scris acum un moment. Dar, luni, ne-am afirmat că putem strecoare înapoi în domeniul eficienței realizarea ceva care este logaritmică poate, sau cel mai bun încă, poate chiar ceva care este așa-numita constantă de timp. Deci, cum putem face acest lucru prin utilizarea acestor noi instrumente, aceste adrese, aceste indicii, și filetare lucrurile noastre proprii? Ei bine, să presupunem că aici, acestea sunt o grămadă de numere pe care le doresc pentru a stoca într-un structură de date și de căutare eficient. Putem derula absolut la săptămână două, arunca aceste într-o matrice, și le căuta folosind căutare binară. Diviza și cuceri. Și, de fapt ai scris căutare binară în PSET3, în cazul în care a implementat programul găsi. Dar știi ce. Există un fel de mai mod inteligent de a face acest lucru. E un pic mai mult sofisticat și, probabil, ne permite să vedem de ce binar căutare este atât de mult mai repede. În primul rând, haideți să introducă noțiunea de copac. Care chiar dacă în copaci realitate un fel de cresc ca aceasta, în lumea de calculator știință au un fel de jos cresc ca un arbore genealogic, în cazul în care aveți bunicii tăi sau bunicii mari sau fleacuri în partea de sus, patriarhul și matriarhatului familiei, cel doar așa-numita rădăcină, nod, mai jos care sunt copiii ei, sub care sunt copiii săi, sau descendenții săi în general. Și oricine agățat partea de jos a familiei copac, pe lângă faptul că cel mai tanar din familie, de asemenea, doar poate fi generic numit frunzele pomului. 

Deci, aceasta este doar o adunatura de cuvinte și definiții pentru ceva numit un copac în calculator știință, la fel ca un arbore genealogic. Dar nu e încarnări crescator de arbori, dintre care unul este numit un arbore binar de căutare. Și vă puteți fel de tease în afară ceea ce face acest lucru. Ei bine, e binar in ce sens? În cazul în care nu provin de la binar aici? Ne pare rău? Nu este atât de mult un fie sau. Este mai mult decât fiecare dintre nodurile are nici mai mult de doi copii, așa cum vom vedea aici. În general, un tree-- și părinții și bunicii voștri poate avea cât mai multe copii sau nepoții ca doresc de fapt, și așa, de exemplu, acolo avem trei copii la nodul dreapta, dar într-un arbore binar, un nod are Zero, una, sau doi copii. maxim Și că este o proprietate frumos, pentru că dacă este limitat de doi, vom fi în măsură să obține o bază de jurnal pic doi acțiune se întâmplă aici în cele din urmă. Deci, avem ceva logaritmică. Dar mai mult pe faptul că într-un moment. Copac de căutare înseamnă că numerele sunt dispuse astfel încât copilul stânga lui Valoarea este mai mare decât rădăcina. Și copilul său chiar este mai mare decât rădăcina. Cu alte cuvinte, dacă lua oricare dintre noduri, cercurile în această imagine, și se uită la stânga sa copil și copilul ei bine, primul trebuie să fie mai mică de, A doua ar trebui să fie mai mare decât. Deci, bun-simț verifica 55. E plecat copil este de 33. E mai puțin de. 55, dreptul său copil este de 77. E mai mare decât. Și că este o definiție recursivă. Am putea verifica fiecare dintre aceste noduri și același model va organiza. 

Deci, ce e frumos într-o arbore binar de căutare, este că unul, putem pune în aplicare cu o struct, la fel ca aceasta. Și chiar dacă suntem aruncat o mulțime de structuri de la dumneavoastră, sunt oarecum intuitiv acum sperăm. Sintaxa este încă arcane sigur, dar conținutul unui nod în acest context-- și păstrăm folosind nodul cuvânt, indiferent dacă este un dreptunghi pe ecran sau un cerc, e doar o container generic, în acest caz de un copac, cum ar fi cea am văzut, avem nevoie de un număr întreg în fiecare dintre nodurile și apoi am nevoie de două indicii de indicare pentru copil stânga și copilul bine, respectiv. Deci, asta e modul în care s-ar putea punerea în aplicare a că într-o struct. Și cum ar putea să o pună în aplicare în codul? Ei bine, haideți să aruncăm o rapid uita-te la acest exemplu mic. Nu este funcțională, dar am copiat și inserat ca structura. Și dacă funcția mea pentru un binar arbore de căutare este numit de căutare, și acest lucru ia două argumente, un număr întreg N și un pointer la un nod, astfel încât un pointer la arborele sau un pointer la rădăcina unui copac, cum pot face despre căutarea pentru N? Ei bine, în primul rând, pentru că eu sunt care se ocupă cu indicii, Am de gând să fac o verificare bun-simț. Dacă egali copac este egal nul, este N în acest copac sau nu in acest copac? Ea nu poate fi, nu? Dacă eu sunt trecut nul, nu e nimic acolo. Am putea la fel de bine doar spune orbește return false. Dacă-mi dai nimic, eu cu siguranță nu pot găsi orice număr N. Deci, ce altceva ar putea să verifica acum? Am de gând să spun și altceva, dacă N este mai puțin de ceea ce este la nodul arborelui că am fost dat valoare N. Cu alte cuvinte, în cazul în care numărul eu sunt cauta, N, este mai mică decât nodul că mă uit la. Și nodul caut la este numit copac, și amintesc de exemplul anterior pentru a ajunge la valoarea într-un pointer, Eu folosesc notația săgeată. Deci, dacă N este mai mică decât săgeata copac N, eu vreau să merg conceptual stanga. Cum îmi exprim în căutarea plecat? Pentru a fi clar, dacă acest lucru este imaginea în cauză, și am fost trecut ca cel mai de sus săgeată care este îndreptat în jos. Asta e pointer meu copac. Mă arătând la rădăcina copacului. Și caut să zicem, pentru numărul 44, în mod arbitrar. Este mai puțin de 44 sau mai mare decât 55, evident? Deci, este mai mică de. Și așa mai departe acest lucru, dacă se aplică condiție. Deci conceptual, ceea ce vreau să Căutare următor dacă caut 44? Da? 

Exact, vreau să căutare copilul din stânga, sau sub-arborele din stânga al această imagine. Și, de fapt, să-mi prin imaginea aici pentru o clipă, deoarece Nu pot zgâria asta. Dacă aș începe aici, la 55, și Știu că valoarea 44 Caut este de a stânga, e un fel de rupere ca cartea de telefon în jumătate sau ruperea arborelui în jumătate. Nu mai am să-i pese acest întreg jumătate de copac. Și totuși, curios în ceea ce privește structură, acest lucru aici că începe cu 33, care se este un arbore binar de căutare. I-am spus cuvântul recursiv înainte, din cauza într-adevăr, aceasta este o structură de date care prin definiție este recursivă. S-ar putea avea un copac care este această mare, dar fiecare dintre copii săi reprezintă un copac doar un pic mai mic. În loc de a fi bunicului ea sau bunica, acum e doar mama sau-- Nu pot nu say-- mama sau tata, care ar fi ciudat. În schimb, doi copii de acolo ar fi ca frate și frate. O nouă generație a arborelui genealogic. Dar structural, e aceeași idee. Și se pare că am o funcție cu care am pot căuta o căutare binară copac. Este numit de căutare. Caut N în copac săgeată stânga altfel daca N este mai mare decât valoarea că sunt în prezent la. 55 în povestea în urmă cu o clipă. Am o funcție numită căutare care pot doar trece N acest lucru și caută recursiv sub-copac și doar revenirea indiferent de răspunsul. Mai am unele cazuri de bază finală aici. 

Care este situația finală? Copac este fie nul. Valoarea Mă fie căutați este mai puțin decât sau mai mare decât cea sau egală cu aceasta. Și am putea spune egal egal, dar în mod logic e echivalent cu a spune altceva aici doar. Atât de adevărat este cum mi se pare ceva. Deci sperăm că acest lucru este un chiar mai convingătoare exemplu decât funcția sigma prost am facut cateva cursuri spate, în cazul în care a fost la fel de usor de utilizat o buclă să numere Toate numerele de la un să N. Aici cu o structură de date că în sine este recursiv definite și recursiv trase, acum ne-am au capacitatea de a ne exprima în cod care în sine este recursiv. Deci, acesta este același cod exact aici. 

Deci, ce alte probleme putem rezolva? Deci, un pas rapid departe de copaci pentru doar un moment. Aici este, spun, pavilion german. Și există în mod clar o model de acest flag. Și există o mulțime de steaguri din lume care sunt la fel de simplu ca acest lucru din punct de vedere de culori și modele lor. Dar să presupunem că acest lucru este stocat ca un .GIF, Sau un JPEG, sau bitmap, sau un ping, orice format de fișier grafic cu care esti familiarizat, dintre care unele suntem joc cu în PSET4. Acest lucru nu pare util pentru a stoca pixel negru, pixel negru, pixel negru, dot, dot, dot, o grămadă de pixeli negri pentru prima scanline, sau rând, apoi o grămadă de același, apoi o grămadă de același, și apoi o grămadă de pixeli roșii, pixeli roșu, roșu pixeli, apoi un întreg grămadă de pixeli galbene, galben, nu? 

Nu e astfel de ineficiență aici. Cum ați intuitiv comprima pavilion german dacă o pune în aplicare ca o imagine? Ca ceea ce informații nu putem deranja stocarea pe disc în ordine pentru a reduce dimensiunea fișierului de la noastră ca un megabyte la un kilobyte, ceva mai mic? În care se află concediere aici pentru a fi clar? Ce ai putea face? Da? Exact. De ce nu, mai degrabă decât amintesc culoarea fiecare pixel al naibii de la fel ca faci in PSET4 cu formatul de fișier bitmap, de ce nu te reprezinta coloana din stânga de pixeli, de exemplu o grămadă de pixeli negri, un buchet de culoare roșie, și o grămadă de galben, și apoi doar codifica cumva Ideea de a repeta acest 100 de ori sau repeta acest 1000 de ori? În cazul în care 100 sau 1000 este doar un număr întreg, astfel încât să poate ajunge departe cu doar un singur număr în loc de sute sau mii pixeli de suplimentare. Și într-adevăr, asta e modul în care ar putea comprima pavilion german. Și Acum, ce putem spune despre drapelul francez? Și un pic de un fel de exercitiu mental, care de pavilion pot fi comprimate mai mult pe disc? Pavilion german sau francez pavilion, dacă luăm această abordare? Pavilion german, pentru că există mai redundanță orizontală. Și de proiectare, mulți fișier grafic formate funcționează într-adevăr linii de scanare ca orizontal. Ei ar putea lucra vertical, umanitatea doar cu ani în urmă a decis că vom în general, cred că de lucruri rând de rând în loc de coloană cu coloană. Deci, într-adevăr, dacă ai fi fost să se uite la fișierul mărimea unui pavilion german și francez pavilion, atât timp cât rezoluția este același, aceeași lățime și înălțimea, aceasta aici va fi mai mare, pentru că Trebuie să vă repetați de trei ori. Trebuie să specificați albastru, repetați le alb, repeta le roșu, repeta-te. Nu poți să mergi tot drumul spre dreapta. Și, ca o paranteza, de a face clar de compresie este peste tot, în cazul în care acestea sunt patru cadre de la un video-- te s-ar putea aminti că un film sau video este, în general cum ar fi 29 sau 30 de cadre pe secundă. E ca o carte de flip pic în cazul în care vedea doar imaginea, imagine, imagine, imagine, imagine doar super-rapid, astfel se pare ca actorii de pe ecran sunt în mișcare. Iată un bondar pe partea de sus a un buchet de flori. Și, deși ar putea fi un fel de greu pentru a vedea la prima vedere, singurul lucru se deplasează în acest film este albina. 

Ce este prost despre stocarea imagini video necomprimate,? E un fel de deșeuri pentru a stoca filme ca patru imagini aproape identice care diferă numai în măsura în care albina este. Puteți arunca mai de aceste informații și amintiți-vă doar, de exemplu, primul cadru și ultimul cadru, cadre cheie dacă ați auzit vreodată cuvântul, și doar magazin din mijloc în cazul în care albina este. Și nu trebuie să stoca toate roz, și albastru, și Valorile verzi, de asemenea. Deci, acest lucru este de a spune doar că compresie este peste tot. Este o tehnica de multe ori am folosi sau de a lua de la sine aceste zile. 

Dar cum a face tu comprima text? Cum te duci despre comprimarea text? Ei bine, fiecare dintre personajele din ASCII este un octet, sau opt biți. Și asta e un fel de prost, nu? Pentru că, probabil, de tip A și E și I și O și U o mulțime mai des decât ca W sau Q sau Z, în funcție de limba în care scrii cu siguranță. Și atunci de ce suntem folosind opt biți pentru fiecare literă, inclusiv cel mai puțin scrisori populare, nu? De ce nu folosiți mai puțini biți pentru Super populare litere, cum ar fi e, lucrurile pe care le ghici pentru prima dată în Roata Norocului, și de a folosi mai multe biți pentru cele mai puțin populare literele? Ce? Pentru ca suntem doar de gând să le folosesc mai rar. 

Ei bine, se pare că au fost făcute încercări de a face acest lucru. Și dacă vă amintiți de la clasa școală sau liceu, codul Morse. Codul Morse a puncte și linii care poate fi transmise de-a lungul unui fir ca sunete sau semnale de un fel. Dar codul Morse este un super curat. E un fel de sistem binar în că aveți puncte sau liniuțe. Dar dacă vezi, de exemplu, două puncte. Sau, dacă credeți că înapoi la operatorul care merge ca bip, bip, bip, beep, lovind un pic de declanșare care transmite un semnal, dacă, destinatarul primește două puncte, ce mesaj ați primit? Complet arbitrar. 

I? I? Sau ce about-- sau eu? Poate a fost doar doi dreptate E lui? Deci nu e problema de Decodării cu Morse Codul, cu excepția cazului în care persoană să vă trimită un mesaj de fapt, o pauză, astfel încât să puteți sorta de vedea sau auzi golurile dintre litere, nu este suficient doar pentru a trimite un flux de zerouri și cele, sau puncte și linii, pentru că există ambiguitate. E este un singur punct, așa că, dacă vedea două puncte sau auzi două puncte, Poate că e de două E sau poate e un I. Deci, avem nevoie de un sistem care este un puțin mai mult inteligent decât atât. Deci, un om pe nume Huffman ani Acum a venit cu exact acest lucru. Deci, noi suntem doar de gând să ia o privire rapidă la modul în care copacii sunt germane la acest lucru. Să presupunem că acest lucru este unele Mesajul prost doriți să trimiteți, compusă din doar A, B, D C S și lui E, dar există o mulțime de concediere aici. Nu este menit să fie limba engleză. Nu e criptat. E doar un mesaj prost cu o mulțime de repetiție. Deci, dacă te numeri efectiv tot A lui, E lui lui B, C lui, D, și, iată frecvența. 20% dintre literele sunt A lui, 45% din scrisorile sunt E lui, și alte trei frecvențe. Am numărat acolo manual și doar a făcut calculele. 

Deci, se dovedește că Huffman, ceva timp în urmă, a dat seama că, știți ceea ce, în cazul în care încep de construcție un copac, sau padure de copaci, dacă vreți, după cum urmează, pot face următoarele. Am de gând să dea un nod la fiecare scrisorilor pe care le pasă și am de gând pentru a stoca în interiorul acestui nod frecvențele ca un punct de flotant valoare, sau ai putea folosi o N, de asemenea, dar vom folosi doar un float aici. Și algoritmul care el a propus este că să ia această pădure de nod unic copaci, copaci, astfel super-scurt, și de a începe să le cu conectarea grupuri noi, noi părinții, dacă vrei. Și faci asta prin alegerea două mai mici frecvențe la un moment dat. Așa că am luat 10% și 10%. Am crea un nou nod. Și fac apel noul nod de 20%. 

Care două noduri combina viitoare? E un pic ambiguu. Deci nu e unele cazuri colț ia în considerare, dar pentru a menține lucrurile destul de, Am de gând să aleagă 20% - Acum am ignora pe copii. Am de gând să aleagă 20% și 15% și să tragă două noi muchii. Și acum două noduri care pot combina în mod logic? Ignorați toți copiii, toate nepoți, doar uita-te la rădăcini acum. Care două noduri pot lega împreună? Punct de două și 0,35. Deci lasă-mă să elaboreze două noi muchii. Și apoi am doar un singur stângă. Deci, aici e un copac. Și a fost întocmită în mod deliberat să se uite un fel de frumos, dar observați că marginile au De asemenea, a fost etichetate zero și unu. Deci toate marginile rămase sunt zero arbitrar, dar în mod constant. Toate marginile din dreapta sunt cele. 

Și așa mai departe ceea ce a propus Hoffman este, dacă doriți să reprezinte un B, mai degrabă decât reprezintă numărul 66 ca ASCII care este de opt biți întregi, Știi ce, doar magazin modelul de zero, zero, zero, zero pentru că asta e calea din copacul meu, domnul copac Huffman lui, la frunza de la rădăcină. Dacă doriți să stocați un E, prin contrast, nu trimite opt biți care reprezintă un E. În schimb, trimite ce model de biți? Unul. Și ce e frumos despre acest lucru este că E este cel mai popular scrisoare, și utilizați cel mai scurt codul pentru el. Următoarea mai populare scrisoare pare ca a fost A. Și câți biți -a propus utilizarea pentru asta? Zero, unul. 

Și pentru că este pus în aplicare ca acest copac, de acum lasă-mă să prevadă există nici o ambiguitate ca în Morse cod, deoarece toate scrisori care vă interesează sunt la finalul acestor margini. Deci asta e doar o aplicarea unui copac. Acest este-- și voi val mâna mea la acest modul în care s-ar putea să pună în aplicare acest lucru ca pe o structură C. Avem nevoie doar de a combina un simbol, ca un char, și frecvența în stânga și dreapta. Dar să ne uităm la două exemple finale pe care le vei obține destul de familiarizat cu după test zero în problema set de cinci. 

Deci, nu există structura de date cunoscut ca un tabel hash. Și un tabel hash este un fel de se răcească în care acesta are pistoane. Și să presupunem că e patru găleți aici, doar patru spații goale. Iată un pachet de cărți, și aici este club, cazma, club, diamante, club, diamante, club, diamante, astfel clubs-- aceasta este aleatorie. Hearts, hearts-- așa că eu sunt bucketizing toate intrările aici. Și are nevoie de masă hash să se uite la dvs. de intrare, și apoi pune-l într-o anumită loc pe baza ceea ce vezi. Este un algoritm. Și am fost folosind un super algoritm vizual simplu. Cea mai grea parte a care a fost amintindu care au fost imaginile. Și apoi există patru lucruri totale. 

Acum stive au fost în creștere, care este un lucru de design deliberat aici. Dar ce altceva s-ar putea să fac? Deci, de fapt, aici avem o grămadă de cărți de examen Old School. Să presupunem că o grămadă de Numele elevilor sunt pe aici. Iată un tabel hash mai mare. În loc de patru pistoane, Am, să spunem 26. Și nu am vrut să merg împrumute 26 lucruri din afara [? Annenberg?], Așa aici e cinci, care reprezintă Un prin Z. Și dacă vezi un student al cărui nume începe cu A, Am de gând să lui sau test pus acolo. Dacă cineva începe cu C, acolo, Un-- de fapt, nu a vrut să fac asta. B merge aici. Deci am A și B și C și Acum, aici e un alt student A. Dar dacă acest tabel hash este puse în aplicare cu o matrice, Sunt un fel de filetat în acest moment, nu? Am facut un fel de nevoie de a pune această undeva. 

Deci, într-un fel eu pot rezolva acest lucru este, toate drept, A este ocupat, B este ocupat, C este ocupat. Am de gând să-l pună în D. Deci, la în primul rând, am acces instant aleator la fiecare dintre gălețile pentru studenți. Dar acum e un fel de descentralizat în ceva liniar, pentru că dacă vreau pentru a căuta pe cineva al cărui nume începe cu A, am verifica aici. Dar dacă acest lucru nu este A Student caut, Am facut un fel de trebuie să începe verificarea gălețile, pentru că ceea ce am făcut a fost un fel de liniar sonda structura de date. Un mod stupid de a spune doar uita-te pentru prima deschidere disponibile, și a pus ca un plan B, ca să spunem așa, sau plan de dezvoltare în acest caz, valoarea în acel loc în loc. Acesta este doar astfel încât, dacă ați Trebuie 26 locații și nici elevi cu Q nume sau Z, sau ceva de genul că, cel puțin pe care îl utilizați spațiul. 

Dar am văzut deja mai mult soluții inteligente de aici, nu? Ce ai face loc dacă aveți o coliziune? Dacă doi oameni au nume A, ceea ce ar fi au fost mai inteligent sau soluție intuitivă decât Punerea o în cazul în care D ar trebui să fie? De ce nu mă duci în afara [? Annenberg?], ca malloc, un alt nod, pune-l aici, și a pus apoi că un student aici. Așa că am, în esență, un fel de o matrice, sau poate mai mult elegant ca suntem pornire pentru a vedea o listă legată. 

Și așa o masă hash este o structură care ar putea arata exact ca aceasta, dar mai inteligent, ai ceva numit înlănțuire separat, prin care un tabel hash pur și simplu este o matrice, fiecare dintre ale cărui elemente nu este un număr, este ea însăși o listă legată. Astfel încât să obțineți acces super rapid decide unde să hash valoare la. La fel ca în exemplul carduri, Am luat decizii foarte rapide. Hearts merge aici, diamante merge aici. La fel aici, A merge aici, D merge aici, B merge aici. Deci, super rapid uite-up-uri, și în cazul în care se întâmplă pentru a rula într-un caz coliziuni în cazul în care ați luat-o, două persoane cu același nume, și apoi doar de a începe asocierea acestora împreună. Și poate vă păstrați-le sortate în ordine alfabetică, poate că nu. Dar cel puțin acum avem dinamismul. Deci, pe de o parte, avem super rapid constantă de timp, și un fel de timp liniar implicat în cazul în care aceste liste legate începe pentru a obține un pic cam lung. 

Deci, acest fel de prostie, ani în urmă. geeky glumă La CS50 hack-a-Thon, atunci când elevii check-in, unele TF sau CA în fiecare an crede că e amuzant să pună un semn ca aceasta, în cazul în care doar înseamnă că dacă numele tău începe cu un A, du-te în acest fel. Dacă numele tău începe cu un B, du-te astea-- OK, e amuzant Poate mai târziu în semestrul. Dar există o altă mod de a face acest lucru, de asemenea. Întoarce-te la asta. 

Deci, există această structură. Și aceasta este ultima noastră structură pentru ziua de azi, care este ceva numit un trie. T-R-I-E, care din anumite motive este scurt pentru recuperare, dar se numește trie. Deci, un trie este un alt interesant amalgam de o mulțime de aceste idei. Este un copac, pe care le-am văzut înainte. Nu este un arbore binar de căutare. Este un copac cu orice număr de copii, dar fiecare dintre copii într-o trie este o matrice. O serie de dimensiuni, spun, 26 sau poate 27 dacă doriți să sprijine nume despărțite sau apostrofuri în numele oamenilor. 

Și așa este o structură de date. Și dacă te uiți de sus în jos, cum ar fi dacă ați uita-te la nodul de sus acolo, M, este arătând spre stânga lucru acolo, care este apoi A, X, W, E, L, L. Acest lucru este doar o structură de date care în mod arbitrar este stocarea numele oamenilor. Și Maxwell sunt stocate de doar în urma o cale de matrice pentru a matrice de matrice. Dar ceea ce este uimitor cu privire la un trie este că, în timp ce o listă legată și chiar o matrice, cel mai bun am ajuns vreodată este timp liniar sau de timp logaritmică căutarea cineva. În această structură de date a unui trie, în cazul în care structura mea de date are un nume în ea și caut Maxwell, eu sunt O să-l găsim destul de repede. Mă uit doar pentru M-A-X-W-E-L-L. Dacă această structură de date, prin contrast, dacă N este un milion, dacă există o milioane de nume în această structură de date, Maxwell este încă va fi detectabil după doar M-A-X-W-E-L-L pași. Și etapele David-- D-A-V-I-D. Cu alte cuvinte, prin construirea o structură de date care este Trebuie de care toate aceste tablouri, toate se intretine cu acces aleator, Pot începe căutarea în sus lui oameni numele folosind o cantitate de timp în care este proporțional cu numărul de nu de lucruri în structura de date, ca un milioane de nume existente. Durata de timp este nevoie de mine pentru a găsi M-O-X-W-E-L-L în această structură de date este proporțională nu cu Dimensiunea de structura de date, dar la lungimea numelui. Și realist Numele ne uităm în sus nu sunt niciodată de gând să fie nebun lung. Poate cineva are un caracter de 10 numele, 20 nume de caractere. Este cu siguranță finit, nu? Există un om de pe Pamant, care are cel mai lung nume posibil, dar numele este o constantă lungime valoare, nu? Nu variază în nici un sens. Deci, în acest fel, am realizat o structură de date care este constantă de timp uite-up. Aceasta nu ia o serie de măsuri în funcție de lungimea de intrare, dar nu numărul numelui în structura de date. Deci, dacă ne-am dubla numărul de nume anul viitor, de la un miliard la două miliarde de euro, constatare Maxwell este de gând să ia același număr exact de șapte pași să-l găsească. Și așa se pare că am atins Graal nostru sfânt de timpul de funcționare. 

Deci, un cuplu de anunțuri rapid. Quiz zero, se apropie. Mai multe pe site-ul care pe parcursul a în următoarele două zile. De luni lecture-- Este o sărbătoare aici, la Harvard luni. Nu e în New Haven, așa că luați clasa la New Haven pentru prelegere luni. Totul va fi filmat și transmisă în direct, ca de obicei, dar să se încheie astăzi cu un al doilea clip de 30 numitele "Gânduri profunde" de Daven Farnham, care a fost inspirat anul trecut de sâmbătă "Gânduri adânci" Night Live de de Jack Handy, care ar trebui să facă acum un sens. 

FILM: Și acum, "Deep Gânduri "de Daven Farnham. Tabel hash. 

SPEAKER 1: Bine, asta e de acum. Ne vedem săptămâna viitoare. 

DOUG: să-l văd în acțiune. Deci, haideți să aruncăm o privire la asta acum. Deci, aici, avem o serie nesortate. 

IAN: Doug, pot merge mai departe și repornire acest lucru pentru doar o secundă, vă rog. Bine, camere sunt de rulare, astfel încât acțiune ori de câte ori sunteți gata, Doug, bine? DOUG: Bine, deci ceea ce am avem aici este o matrice nesortate. Și am colorat toate elementele roșu pentru a indica faptul că acesta este, de fapt, nesortate. Deci amintesc că primul lucru pe care o facem este ne sorta jumătatea stângă a tabloului. Apoi ne-am sorta dreapta jumătate din matrice. Și Ya-da, Ya-da, Ya-da, le merge împreună. Și avem o gamă complet sortat. Deci așa merge sort funcționează. 

IAN: Ho, ho, ho, cut, cut, cut, tăiate. Doug, nu poți doar Ya-da, Ya-da, Ya-da, ți de drum prin îmbinare fel. 

DOUG: Tocmai am făcut-o. Este bine. Suntem bine să mergem. Să păstreze rulare. Deci, oricum, 

IAN: Trebuie să explice mai deplin decât atât. Asta nu e suficienta. DOUG: Ian, noi nu Trebuie să mă întorc la o. Este bine. Deci, oricum, dacă vom continua cu merge-- Ian, suntem în mijlocul filmare. 

IAN: Știu. Și nu putem doar Ya-da, Ya-da, Ya-da, prin întregul proces. Trebuie să explice modul în care cele două părți se fuzionat împreună. 

DOUG: Dar am deja a explicat modul în care două sides-- 

IAN: Ai doar afișate le o gamă merge. DOUG: Ei știu procesul. Sunt bine. Am trecut peste asta de zece ori. 

IAN: Tocmai ai sărit chiar peste ea. Mergem înapoi la unul, nu poți Ya-da, da-Ya peste el. Bine, înapoi la unul. 

DOUG: Am să mă întorc prin toate slide-uri? Dumnezeul meu. E ca și cum a șasea oară, Ian. Este bine. 

IAN: Bine. Ești gata? Grozav. Acțiune.