>> SPEAKER 1: Bine, deci ne-am întors.
Bine ati venit la CS50.
Acesta este sfârșitul de săptămâna de șapte.
Astfel amintesc că ultima dată, am început uita la ceva mai sofisticat
structuri de date.
Deoarece până acum, tot ce am avut într-adevăr la dispoziția noastră a fost aceasta, o matrice.
>> Dar, înainte de a renunța matrice ca nu tot ce interesant, care într-adevăr
de fapt este, ce sunt unele din plusuri de aceste date simple
Structura astfel acum?
Ce e asta bine la?
Măsura în care am văzut-o?
Ce ai?
Nimic.
>> STUDENT: [inaudibil].
>> SPEAKER 1: Ce e asta?
>> STUDENT: [inaudibil].
>> SPEAKER 1: dimensiune fixă.
OK, deci de ce este dimensiunea fixă ​​bine, deși?
>> STUDENT: [inaudibil].
>> SPEAKER 1: OK, deci este eficient în sensul că se poate aloca un
sumă fixă ​​de spațiu, care, sperăm, Este exact la fel de mult
spațiu, după cum doriți.
Astfel că ar putea fi absolut un plus.
>> Ce este o altă parte dintr-o serie?
Da?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Toate - Îmi pare rău?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Toate cutiile din memorie sau unul lângă celălalt.
Și că este util - de ce?
Asta e destul de adevărat.
Dar cum putem exploata acest adevăr?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Exact, putem urmări unde totul este doar prin cunoașterea
o adresă, și anume adresa Primul octet din segment de memorie.
Sau în cazul șir, adresa primului
char în șir.
Și de acolo, putem găsi sfârșitul șirului.
Putem găsi doilea element, al treilea element, și așa mai departe.
>> Și așa mod fantezist de a descrie ce caracteristică este că matrice ne da
acces aleator.
Doar prin utilizarea paranteză notație și un număr, puteți sări la
un element specific în matrice în timp constant, Big O
de una, ca să spunem așa.
>> Dar există unele dezavantaje.
Ce un tablou nu face foarte usor?
Ce nu e bine la?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Ce-i asta?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Extinderea în dimensiune.
Astfel dezavantajele de matrice sunt exact opusul a ceea ce
Upsides sunt.
Deci, unul din dezavantaje este că este o dimensiune fixă.
Deci, nu se poate dezvolta cu adevarat.
Puteți realoca o bucată mai mare de memorie, iar apoi mutați elemente vechi
în noua matrice.
Și apoi liber matrice vechi, pentru exemplu, prin utilizarea malloc sau unul similar
Funcția numit realloc, care realoce memorie.
>> Realloc, ca o parte, încearcă să-ți dea memorie, care e lângă matrice
pe care le au deja.
Dar s-ar putea muta lucrurile în jurul totul.
Dar, în scurt, că e scump, nu?
Pentru că, dacă aveți o bucată de memorie de această dimensiune, dar vrei cu adevarat unul
de această dimensiune, și doriți să păstrați elementele originale, trebuie
aproximativ un proces liniar de copiere timp care trebuie să se întâmple de la
matrice vechi la nou.
Și realitatea se cere de operare sistem nou și din nou și
din nou pentru bucăți mari de memorie poate începe să te coste ceva timp, de asemenea.
Deci, este atât o binecuvântare și un blestem în ascunde, faptul că aceste tablouri
sunt de dimensiuni fixe.
Dar, dacă vom introduce în schimb ceva ca aceasta, pe care am numit-o legat
lista, vom obține câteva upsides și câteva dezavantaje aici.
>> Deci, o lista inlantuita este pur și simplu de date structură formată dintr-o structura C în acest
caz, în cazul în care un struct, rechemare, este doar un recipient pentru unul sau mai specifice
tipuri de variabile.
În acest caz, ceea ce face tipurile de date par a fi interiorul struct care
Ultima dată când am numit un nod?
Fiecare dintre aceste dreptunghiuri este un nod.
Și fiecare dintre dreptunghiuri mai mici în interiorul acestuia este un tip de date.
Ce tipuri am spus ei au fost luni?
Da?
>> STUDENT: [inaudibil].
>> SPEAKER 1: O variabilă și un pointer, sau mai precis, un int, pentru n,
și un indicator în partea de jos.
Atât de cei care se întâmplă să fie 32 de biți, la cel puțin pe un calculator ca aceasta CS50
Aparat, și așa sunt atras în mod egal în mărime.
>> Deci, ce sunt folosind indicatorul deși pentru aparent?
De ce adăuga acest săgeată acum, când tablouri au fost atât de frumos și curat și simplu?
Ce este indicatorul face pentru ne în fiecare dintre aceste noduri?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Întocmai.
Ea îți spune unde următoarea este.
Asa ca am un fel de analogia de folosind un fir pentru a sorta de
firul acestor noduri împreună.
Și asta este exact ceea ce facem cu indicii deoarece fiecare dintre acestea
bucăți de memorie pot sau nu să fie învecinate, spate în spate în spate
interior de RAM, pentru că de fiecare dată când apel malloc zis, da-mi destul de
octeți pentru un nod nou, s-ar putea fie aici, sau ar putea fi aici.
Ar putea fi aici.
Tu chiar nu știu.
>> Dar folosind indicii în adresele aceste noduri, puteți cusatura le
împreună într-un mod care arată vizual ca o lista, chiar dacă aceste lucruri sunt
tot răspândit de-a lungul unul sau două sau cu cele patru GB de memorie RAM
în interiorul propriul computer.
>> Deci dezavantaj, atunci, de o lista inlantuita este ceea ce?
Ce este un preț suntem aparent de plată?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Mai mult spatiu, nu?
Am, în acest caz, a dublat suma de spațiu pentru că am plecat
de la 32 de biți pentru fiecare nod, pentru fiecare Int, asa ca acum 64 de biți pentru că trebuie să
să păstreze în jurul un indicator la fel de bine.
Ai mai multă eficiență dacă struct dvs. este mai mare decât acest lucru simplu.
Dacă aveți de fapt, un elev în interiorul care este o pereche de siruri de caractere pentru
numele și casa, poate, un număr de identificare, poate că unele alte domenii cu totul.
>> Deci, dacă aveți un struct suficient de mare, atunci poate costul indicatorul este
nu o astfel de afacere mare.
Acesta este un pic de un caz colț în care suntem stocarea unui astfel de simplu primitiv
interiorul listei legat.
Dar ideea este aceeași.
Tu cu siguranta mai multe cheltuieli memorie, dar vei primi
flexibilitate.
Pentru că acum, dacă vreau să adăugați un element la începutul acestei liste,
Am să aloce un nou nod.
Și trebuie să actualizeze doar cei săgeți într-un fel de mișcare doar
câteva indicii în jurul valorii.
>> Dacă vreau să introduceți ceva în mijlocul listei, eu nu trebuie să
împinge toată lumea la o parte asa cum am facut in trecut săptămâni cu voluntarii nostri, care
a reprezentat o matrice.
Eu pot aloca doar un nou nod și apoi doar punctul de săgețile în
direcții diferite, deoarece nu trebuie să rămână în actuala
memorie o linie adevarat ca am desenat l aici pe ecran.
>> Și apoi în cele din urmă, în cazul în care doriți să inserați ceva la sfârșitul listei, e
chiar mai ușor.
Aceasta este un fel de notație arbitrare, dar indicatorul 34, să ia o presupunere.
Care este valoarea indicatorului sa cea probabil fel trase de ca un vechi
antena școală acolo?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Este, probabil, nul.
Și într-adevăr că este un autor reprezentarea nul.
Și este nul, deoarece absolut Trebuie să știu unde capătul unui legat
Lista este, ca nu cumva să vă păstrați în urma și urma și ca urmare a acestor săgeți
la o valoare de gunoi.
Deci, null va însemna că nu există nici o mai multe noduri la dreptul de numărul 34,
în acest caz.
>> Deci, noi propunem ca putem pune în aplicare acest nod în cod.
Și am văzut acest tip de sintaxă înainte.
Typedef definește doar un nou tip de ne, ne dă un sinonim cum ar fi
șir a fost pentru char *.
În acest caz, o să ne dea notația prescurtată, astfel încât nodul struct
pot în schimb să fie scris doar ca nod, care este mult mai curat.
Este mult mai puțin detaliat.
>> În interiorul unui nod este aparent un int numit n, iar apoi un nod struct *
ceea ce înseamnă exact ceea ce ne-am dorit săgeți pentru a înțelege, un pointer la un alt
nod de exact același tip de date.
Și eu propun ca am putea pune în aplicare o funcția de căutare cum ar fi aceasta, care, la
prima vedere ar putea părea un pic mai complex.
Dar haideți să-l în context vedea.
>> Lasă-mă să merg pe la aparatul aici.
Lasă-mă să deschid un fișier denumit Lista de zero punct ore.
Și care conține numai definiția ne doar văzut acum un moment pentru aceste date
tip numit un nod.
Deci, ne-am pus că într-un h Fisier punct.
>> Și ca o parte, chiar dacă această Programul pe care esti pe cale de a vedea este
Nu toate că complex, este într-adevăr convenție atunci când scrieți un program pentru
pune lucrurile cum ar fi tipurile de date, pentru a trage constante, uneori, în interiorul dvs.
fișier antet și nu neapărat în fișierul C, cu siguranță atunci când vă
Programele obține mai mari și mai mari, astfel încât știi unde să te uiți atât pentru
Documentația în unele cazuri, sau pentru elementele de bază, cum ar fi acest lucru,
definiție de un anumit tip.
>> Dacă am deschide lista de zero puncte C, observa câteva lucruri.
Acesta include câteva fișiere antet, cele mai multe din care am văzut înainte.
Acesta include propriul fișier antet.
>> Și, ca o paranteză, de ce e dublu citate aici, spre deosebire de unghiul
paranteze pe linia care Am subliniat acolo?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Da, așa este un fișier local.
Deci, dacă este un fișier local de propria dvs. aici pe linia 15, de exemplu, să utilizați
ghilimelele duble în loc dintre paranteze.
>> Acum, acest lucru este un fel de interesant.
Observați că am declarat-o la nivel mondial variabilă în acest program de pe linia 18
denumit în primul rând, ideea fiind acest lucru este O să fie un pointer la primul
nod în lista mea legată, și am inițializat la null, pentru că am
Nu alocat nici un real noduri încă.
>> Deci, aceasta reprezintă, pictural, ceea ce văzut acum un moment în imagine ca
că indicatorul pe departe in partea stanga.
Deci, chiar acum, ca indicatorul nu are o săgeată.
Este în schimb, este doar nul.
Dar aceasta reprezintă ceea ce va fi adresa primului real
nod în această listă.
Așa că l-am implementat este un nivel global pentru că, după cum veți vedea, toate acestea
Programul are în viață este punerea în aplicare a o listă legat de mine.
>> Acum, am câteva prototipuri aici.
Am decis să pună în aplicare caracteristici cum ar fi ștergere, inserare, căutare, și
traversal -
ultimul fiind doar mers pe jos peste lista, imprimarea elementele sale.
Și acum, aici e rutina mea principală.
Și nu vom petrece prea mult timp pe acestea, deoarece aceasta este un fel de, sperăm
pălărie veche de acum.
>> Am de gând să fac următoarele, în timp ce utilizatorul cooperează.
Deci unul, am de gând să imprima în acest meniu.
Și l-am formatat ca curat ca am putut.
Dacă utilizatorul tastează într-o singură, înseamnă că care doriți să o ștergeți ceva.
Dacă utilizatorul tastează în două, înseamnă că care doriți să îl inserați ceva.
Și așa mai departe.
Am de gând să solicite apoi apoi pentru o comandă.
Și apoi am de gând să utilizeze getint.
>> Deci, aceasta este o foarte simplu de meniuri interfață în cazul în care trebuie doar să tastați
un număr de cartografiere la o acestor comenzi.
Și acum am un comutator frumos curat Declarația care va porni
indiferent de utilizatorul tastat inch
Și dacă au scris unul, voi apel șterge și rupe.
În cazul în care tastat doi, voi apel introduce și rupe.
>> Și acum observați am pus fiecare dintre acestea pe aceeași linie.
Aceasta este doar o decizie stilistice.
De obicei am văzut ceva ca aceasta.
Dar am decis, sincer, programul meu privit mai ușor de citit, deoarece
a fost doar patru cazuri la doar lista aceasta.
Utilizarea total legitim de stil.
Și am de gând să fac acest lucru, atât timp cât utilizatorul nu a tastat la zero, pe care am
a decis va însemna ca doresc sa renunte.
>> Deci, acum observa ce am de gând să faci aici.
Am de gând să elibereze lista aparent.
Dar mai mult pe faptul că într-o clipă.
Să facem mai întâi acest program.
Deci, lasă-mă să fac un terminal de mare fereastră, punct lista slash 0.
Am de gând să merg mai departe și se introduce prin dactilografiere două, un număr asemănător 50, iar acum
veți vedea lista este acum de 50.
Și textul meu doar derulat un pic.
Deci, acum observa lista conține numărul 50.
>> Să facem o altă introduce prin luarea două.
Să tastați în numărul ca unul.
Lista este acum unul, urmată de 50.
Deci, aceasta este doar o reprezentare textuală a listei.
Și să introduceți un număr mai ca numărul 42, care este, sperăm
O să ajung la mijloc, deoarece acest program, în special felul acesta
elemente ca le introduce.
Deci nu îl avem.
Programul de super-simplu care ar putea absolut s-au folosit o matrice, dar eu
se întâmplă să fie folosind o listă înlănțuită doar așa că am putea dinamic
cresc și psihiatru.
>> Deci, haideți să aruncăm o privire de căutare, dacă am rulați comanda trei, vreau să căutați
pentru, să zicem, numărul 43.
Și nimic nu a fost aparent gasit, pentru că m-am întors nici un răspuns.
Deci, hai sa facem acest lucru din nou.
Caută.
Să căutare pentru 50, sau mai degrabă căutare pentru 42, care are o bună
lipsită de sens subtil.
Și am găsit sensul vieții acolo.
Numărul 42, dacă nu știi de referință, pe Google.
Bine.
Deci, ceea ce a facut acest program pentru mine?
Este pur și simplu mi-a permis pentru a insera astfel departe și de căutare pentru elemente.
>> Să repede înainte, apoi, să că funcția am aruncat o privire
, luni, ca un teaser.
Deci această funcție, eu susțin, căutările pentru un element din lista de prima
unul, în care utilizatorul și apoi apel Getint pentru a obține un int real
pe care doriți să căutați.
>> Apoi observa acest lucru.
Am de gând să creeze o variabilă temporară în linie 188 numit pointer -
PTR -
ar fi numit-o nimic.
Și este un pointer la un nod pentru că am spus nod * acolo.
Și eu inițializare să fie egal cu în primul rând, astfel că am efectiv am mea
deget, ca să spunem așa, pe foarte primul element al listei.
Deci, dacă mâna mea aici este PTR am arătând în același lucru pe care în primul rând
este îndreptat la.
>> Deci, acum din nou în cod, ceea ce se întâmplă în continuare -
aceasta este o paradigmă comună atunci când iterarea peste o structură ca o
Lista legate.
Am de gând să fac următoarele în timp ce indicatorul nu este egal cu NULL, de aceea în timp ce
degetul meu nu este îndreptat la un nul valoare, dacă sageata n este egal cu n.
Vom observa în primul rând că n este ceea ce tastat în pe GetInts utilizator numesc aici.
>> Și sageata n ce înseamnă?
Ei bine, dacă ne întoarcem la imaginea de aici, dacă am un deget îndreptat la
ca primul nod care conține nouă, săgeata în esență, înseamnă a merge la care
nod și apuca valoarea la locația n, în acest caz, câmpul de date numit n.
>> Ca o paranteza - și am văzut acest lucru un cuplu de săptămâni în urmă, când cineva a întrebat -
această sintaxă este nouă, dar nu ne da puteri pe care le
nu au deja.
Care a fost această frază echivalentă cu ajutorul punct notație și stele, un cuplu
de săptămâni în urmă, când am detasat-o inapoi acest strat un pic prematur?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Exact, era stele, și apoi a fost stea dot n, cu
paranteze aici, care arată, sincer, cred că o mulțime
mai criptic de citit.
Dar indicatorul stele, ca întotdeauna, înseamnă du-te acolo.
Și odată ce ești acolo, ce date câmp vrei să acceseze?
Ei bine, utilizați notația punct de acces un câmp structs de date, și eu
în mod special vreau n.
>> Sincer, aș spune acest lucru este doar mai greu de citit.
Este mai greu să-și amintească unde face paranteze merge,
stele, și toate astea.
Deci, lumea a adoptat unele sintactic zahăr, ca să spunem așa.
Doar un mod sexy de a spune, aceasta este echivalent, și
probabil, mai mult intuitiv.
Dacă indicatorul este într-adevăr un pointer, săgeată mijloace de notare du-te acolo și de a găsi
domeniul în acest caz numit n.
>> Deci, dacă am găsi, observa ceea ce fac.
Eu pur si simplu imprima, am găsit la suta I, conectarea în valoare pentru că Int.
Eu numesc somn timp de o secundă doar la fel de pauză lucrurile de pe ecran pentru a
da utilizatorului un al doilea pentru a absorbi ceea ce sa întâmplat.
Și apoi m-am rupe.
În caz contrar, ce să fac?
Am actualiza indicatorul la egal săgeata de lângă indicator.
>> Deci, doar pentru a fi clar, acest lucru înseamnă du-te acolo, cu ajutorul meu de notație de școală veche.
Deci, acest lucru înseamnă doar pentru a merge la orice te îndreptat la, care, în foarte
Primul caz este arăt eu la struct cu nouă în ea.
Așa că m-am dus acolo.
Și apoi notația punct înseamnă, obține valoarea la următorul.
>> Dar valoarea, chiar dacă este desenat ca o îngustă, este doar un număr.
Este o adresă numerică.
Deci, aceasta linie de cod, dacă scris ca aceasta, mai criptic
fel, sau ca aceasta, puțin mai mod intuitiv, înseamnă doar mișca mâna mea
de la primul nod la următoarea, și apoi următoarea, și apoi
următorul, și așa mai departe.
>> Deci, nu vom insista pe de altă parte implementari de insera și șterge
și traversal, primele două care sunt destul de implicat.
Și cred că este destul de ușor pentru a obține a pierdut atunci când o fac verbal.
Dar ce putem face aici este încearcă să determine modul în care
cel mai bun de a face acest lucru vizual.
Pentru că eu propun ca, dacă ne doriți să inserați elemente în acest
Lista existente, care are cinci elemente -
9, 17, 22, 26, și 33 -
dacă am fost de gând să pună în aplicare acest lucru în cod, trebuie să ia în considerare modul în care pentru a merge
despre a face acest lucru.
>> Și mi-ar propune luarea de măsuri pentru copii prin care, în acest caz Adică, ce sunt
scenariile posibile pe care le s-ar putea întâlni, în general?
La punerea în aplicare introduce pentru un legat lista, acest lucru se întâmplă doar pentru a fi o
exemplu specific de dimensiunea cinci.
Ei bine, dacă doriți să introduceți un număr, ca spun numărul unu, și
menținerea ordinii sortate, unde evident, nu numărul unu trebuie să
du-te în acest exemplu specific?
Ca la început.
>> Dar ceea ce este interesant este faptul că dacă doriți să introduceți o în acest
lista, ceea ce indicatorul nevoi speciale să fie actualizate aparent?
În primul rând.
Deci, aș spune, acesta este primul caz pe care am putea dori să ia în considerare, un
scenariu care implică introducerea la la începutul listei.
>> Să smulge poate un fel de ușor sau chiar caz mai usor, relativ vorbind.
Să presupunem că doriți să introduceți Numărul 35 în ordine sortată.
Este, evident, aparține acolo.
Deci, ceea ce, evident, indicatorul se va trebuie să fie actualizate în acest scenariu?
Indicatorul 34 a devenit nu null dar adresa struct
care conține numărul 35.
Așa că e cazul doi.
Deci, deja, eu sunt un fel de cuantificarea cât de mult de lucru trebuie să fac aici.
>> Și, în sfârșit, în cazul mijloc evident este Într-adevăr, în mijloc, dacă vreau să
introduce ceva de genul spun 23, care merge între 23 și 26, dar
acum lucrurile devin un pic mai mult implicat pentru că ceea ce
indicii trebuie să fie schimbat?
Deci, 22, evident, trebuie să fie schimbat pentru că el nu mai poate indica 26.
El are nevoie pentru a indica noul nod care Va trebui să aloce de apel
malloc sau ceva echivalent.
>> Dar apoi am nevoie, de asemenea, că noul nod, 23 în acest caz, să aibă pe indicatorul acesteia
arătând la cine?
26.
Și acolo va fi o ordinea de operațiuni aici.
Pentru că dacă fac acest lucru prostește, și eu de exemplu încep de la începutul
lista, iar scopul meu este de a introduce 23.
Și am verifica, îi aparține aici, aproape nouă?
Nu.
Îi aparține aici, alături de 17?
Nu.
Are aparține aici alături de 22?
Da.
>> Acum, dacă eu sunt o prostie aici, și nu gândire acest lucru prin intermediul, am putea
aloca noua mea nod de 23.
S-ar putea actualiza indicatorul de nodul numit 22, arătând
se la noul nod.
Și atunci ce trebuie să actualizeze indicatorul noul nod de a fi?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Exact.
Arătând la 26.
Dar, la naiba, dacă nu au actualizat deja Indicatorul 22 de la punctul de la acest tip, și
acum am orfani, restul a listei, ca să spunem așa.
Deci, ordinea operațiunilor aici va fi important.
>> Pentru a face acest lucru am putut fura, spune, șase voluntari.
Și să vedem dacă nu putem face acest lucru vizual în loc de cod-înțelept.
Si ne-am unele stres minunat bile pentru tine azi.
OK, ce zici de unul, doi, în inapoi - la sfârșitul acolo.
trei, patru, amândoi Tipii de pe final.
Și cinci, șase.
Sigur.
Cinci și șase.
Bine și vom veni cu voi data viitoare.
În regulă, haide sus.
>> Bine, dacă tot ești aici în primul rând, doriți să fie un dur
în Google Glass aici?
În regulă, deci, bine, sticla, înregistra un videoclip.
OK, tu esti bine să plec.
>> În regulă, deci, dacă voi putea veni peste aici, am pregătit în avans
unele numere.
Bine, vino aici.
Și de ce nu te duci un pic în continuare în acest fel.
Și să vedem, care e numele tău, cu sticlă Google?
>> STUDENT: Ben.
>> SPEAKER 1: Ben?
Bine, Ben, va fi primul, literalmente.
Așa că am de gând să vă trimită la sfârșitul etapei.
Bine, și numele tău?
>> STUDENT: Jason.
>> SPEAKER 1: Jason, OK veți fie numărul nouă.
Deci, dacă doriți să urmați Ben în acest fel.
>> STUDENT: Jill.
>> SPEAKER 1: Jill, ai de gând să fie 17, care, dacă am făcut acest lucru mai mult
inteligent, mi-ar fi început la celălalt capăt.
Tu du-te pe acolo.
22.
Și tu ești?
>> STUDENT: Mary.
>> SPEAKER 1: Maria, vei fi 22.
Si numele tau este?
>> STUDENT: Chris.
>> SPEAKER 1: Chris, vei fi 26.
Și apoi în cele din urmă.
>> STUDENT: Diana.
>> SPEAKER 1: Diana, vei fi 34.
Deci, vino aici.
>> În regulă, atât de perfect sortate comanda deja.
Și să mergem mai departe și de a face acest lucru astfel încât să putem într-adevăr -
Ben esti doar un fel de a privi afară, în nicăieri acolo.
OK, deci să mergem mai departe și descrie acest folosind arme, la fel ca am fost, mai exact,
ce se întâmplă.
Deci, mergeți mai departe și să vă o picior sau două dintre voi.
Și mergeți mai departe și punctul cu o singură mână a oricine ar trebui să fie îndreptat la
pe baza acestei.
Și dacă ești nulă doar punctul drept în jos la podea.
OK, asa de bine.
>> Deci, acum avem o listă legat, și lasă-mă să propune ca voi juca rolul de
PTR, asa ca nu va deranja transportă acest jurul.
Și apoi - Convenția prost pe cineva - puteți apela acest tot ce vrei -
indicatorul predecesorul, indicatorul pred -
e doar porecla am dat în Codul nostru de probă la mâna stângă.
De altă parte, care va fi păstrarea urmări de cine este cine în
următoarele scenarii.
>> Deci presupun, în primul rând, vreau să smulge că primul exemplu de inserare, spune
20, în lista.
Așa că am de gând să nevoie de cineva pentru a întruchipează numărul 20 pentru noi.
Așa că am nevoie de cineva malloc din public.
Hai sus.
Care e numele tău?
>> STUDENT: Brian.
>> SPEAKER 1: Brian, bine, astfel încât să este nodul care conține 20.
Bine, vino aici.
Și, evident, în cazul în care face parte Brian?
Deci, în mijlocul - de fapt, așteptați un minut.
Facem asta de ordine.
Vom face acest lucru mult mai greu decât aceasta trebuie să fie la început.
OK, vom liber Brian și realloc Brian ca cinci.
>> OK, deci acum ne-o dorim pentru a insera Brian ca cinci.
Deci, vino aici lângă Ben pentru doar o clipă.
Și tu poți spune probabil în cazul în care această poveste se întâmplă.
Dar să ne gândim cu atenție la ordinea operațiilor.
Și este tocmai această vizuală care se va alinia
cu exemplul de cod.
Deci, aici am PTR îndreptat inițial nu la Ben, per se, ci la orice
apreciază el conține, care în acest caz este - ceea ce este numele tau?
>> STUDENT: Jason.
>> SPEAKER 1: Jason, astfel încât atât Ben și eu sunt arătând spre Jason în acest moment.
Deci, acum trebuie să determine, care face parte Brian?
Așa că singurul lucru pe care am acces la acum este n elementul lui de date.
Așa că am de gând să verifice, este Brian mai puțin de Jason?
Răspunsul este adevărat.
>> Deci, ce acum trebuie să se întâmple, în ordinea corectă?
Am nevoie pentru a actualiza cât de multe indicii În total, în această poveste?
În cazul în care mâna mea este încă îndreptat la Jason, și mâna ta - dacă doriți să
pune mâna cum ar fi, un fel de, I Nu știu, un semn de întrebare.
OK, bine.
>> Bine, deci aveți câțiva candidați.
Fie Ben sau I sau Brian sau Jason sau oricine altcineva, care
indicii nevoie pentru a schimba?
Câte în total?
>> OK, deci doi.
Indicatorul mea nu mai contează cu adevărat pentru că eu sunt doar temporare.
Deci, este doi tipi, probabil, atât Ben și Brian.
Deci, permiteți-mi să propun ca noi actualizam Ben, deoarece el e primul.
Primul element al acestei liste este acum de gând să fie Brian.
Deci, punctul de Ben la Brian.
OK, acum ce?
>> Care devine subliniat la cine?
>> STUDENT: [inaudibil].
>> SPEAKER 1: OK așa Brian are la punctul de la Jason.
Dar am pierdut evidența că indicatorul?
Nu știu unde Jason este?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Eu fac, deoarece sunt indicatorul temporar.
Și probabil, nu s-au schimbat la punctul de la noul nod.
Astfel încât să putem avea pur și simplu Brian punct la cine am îndreptat la.
Și am terminat.
Deci caz unul, introducerea la începutul listei.
Au existat două etape cheie.
Unul, trebuie să actualizeze Ben, și apoi avem, de asemenea, pentru a actualiza Brian.
Și atunci nu trebuie să deranjez plimbatul prin restul de
lista, pentru că am găsit deja sa locație, pentru că el a aparținut
stânga a primului element.
>> În regulă, deci destul de simplă.
De fapt, se simte ca suntem aproape face acest lucru prea complicat.
Deci, haideți să smulgă acum pe final din lista, și să vedem unde
complexitatea începe.
Așa că, dacă acum, am alloc din public.
Oricine vrea să joace 55?
În regulă, am văzut mâna întâi.
Hai sus.
Da.
Care e numele tău?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Habata.
OK, hai sus.
Vei fi numărul 55.
Deci tu, desigur, fac parte la sfârșitul listei.
Deci, haideți să relua simularea cu mine fiind PTR pentru o clipă.
Deci, eu sunt în primul rând de gând să arate la indiferent de Ben pointing la.
Suntem amândoi arătând acum la Brian.
Deci 55 nu este mai mic de cinci.
Așa că am de gând să mă actualiza prin arătând spre viitor indicatorul lui Brian, care
acum este, desigur, Jason.
55 nu este mai mică de nouă, așa Am de gând să actualizeze PTR.
Am de gând să actualizeze PTR Am de gând să actualizeze PTR.
Și am de gând să - hmm, ce-i numele tau din nou?
>> STUDENT: Diana.
>> SPEAKER 1: Diana este îndreptat, desigur, la zero cu mâna stângă.
Deci, în cazul în care nu Habata de fapt, apartin in mod clar?
La stânga, aici.
Deci, cum știu să o pun aici Cred că am greșit.
Pentru că ceea ce este PTR arta acest moment?
Null.
Deci, chiar dacă, vizual, putem evident vezi toate aceste
baieti aici pe scenă.
Nu am ținut cont de precedent persoană din lista.
Nu am un deget subliniind, în acest caz, numărul nodului 34.
>> Să începem de fapt, acest peste.
Așa că acum am de fapt, nu au nevoie de a doua variabile locale.
Și asta este ceea ce veți vedea în codul actual C eșantion, în cazul în care așa cum am merge,
când am actualiza mâna mea dreaptă la punctul Jason, lăsând astfel în urmă Brian, am
începe mai bine folosind mâna stângă pentru a actualiza unde am fost, astfel încât, mă duc
prin această listă -
mai dur decât am intenționat acum aici vizual -
Am de gând să ajung la sfârșitul listei.
>> Această mână este încă nul, care este destul inutil, altele decât pentru a indica
Sunt în mod clar la sfârșitul listei, dar acum cel puțin am asta
indicatorul predecesorul arătând aici, așa acum ceea ce mâinile și ce indicii au nevoie
să fie actualizate?
A cărui mână vrei la primul reconfigura?
>> STUDENT: [inaudibil].
>> SPEAKER 1: OK, deci lui Diana.
În cazul în care vrei să subliniez Indicatorul la stânga Diana de la?
La 55, se presupune, astfel încât am introdus acolo.
Și unde ar trebui să meargă 55 de indicatorul?
Jos, reprezentând nul.
Și mâinile mele, la acest moment, nu contează, pentru că acestea au fost doar
variabile temporare.
Deci, acum am terminat.
>> Deci, complexitatea suplimentare de acolo - și nu e greu de implementat,
dar avem nevoie de o variabilă secundar de a face vă că înainte de a mă muta dreptul meu
de mână, să-mi actualizez valoarea stânga mea parte, indicatorul pred în acest caz, astfel
că am un pointer la final pentru a urmări unde am fost.
Acum, ca o paranteză, dacă te gândești acest prin, acest lucru se simte ca este un
puțin enervant să aibă de a păstra urmări din această mână stângă.
>> Ceea ce ar fi o altă soluție la aceste probleme au fost?
Dacă ai de a restructura datele Structura vorbim
prin chiar acum?
Dacă acest tip doar de simte un pic enervant de a avea, ca, doi pointeri
trece prin lista, cine altcineva ar putea au, într-o lume ideală, menținut
informațiile de care avem nevoie?
Da?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Exact.
Chiar astfel încât nu este de fapt un interesant germeni de o idee.
Și această idee de un pointer anterior, îndreptat la elementul anterior.
Ce se întâmplă dacă am întruchipat că interiorul listei sine?
Și că va fi greu de vizualizat acest lucru fără toată hârtia
care se încadrează la podea.
Dar să presupunem că acești oameni folosit atât de mâinile lor pentru a avea un precedent
pointer, iar un pointer viitor, astfel punerea în aplicare a ceea ce vom numi un dublu
Lista legate.
Asta mi-ar permite pentru a sorta de înapoi, mult mai ușor, fără mine,
programator, având pentru a menține urmări manual -
cu adevărat manual -
de unde am fost anterior În lista.
Deci, nu vom face asta.
Vom păstrați-l simplu, pentru că Va veni la un preț de două ori mai
mult spațiu pentru indicii, dacă vrei un al doilea.
Dar asta e într-adevăr un comun structura de date cunoscut ca un
de două ori lista de legat.
>> Să facem un exemplu final de aici și pune- tipii ăștia din mizerie lor.
Deci, malloc 20.
Haide sus de culoar acolo.
În regulă, care e numele tău?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Imi pare rau?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Demeron?
OK vin pe sus.
Tu trebuie să fie de 20.
Tu, evident, se vor aparțin între 17 și 22.
Deci, lasă-mă să învețe lecția mea.
Am de gând să înceapă indicatorul arătând la Brian.
Și am de gând să aibă mâna stângă actualiza doar la Brian cum am muta la
Jason, verificarea are 20 de mai puțin de nouă?
Nu.
Este 20 mai puțin de 17?
Nu.
Este 20 mai puțin de 22?
Da.
Deci, ce indicii sau mâini nevoie pentru a schimba unde se indică acum?
>> Deci, putem face 17 arătând la 20.
Așa că e bine.
Unde vrem să sublinieze indicatorul acum?
La 22.
Și știm unde 22 este, din nou, datorită la indicatorul mea temporar.
Deci suntem bine acolo.
Deci, din cauza acestei depozitare temporară Am ținut evidența în care toată lumea este.
Si acum poti sa te duci vizual în cazul în care faci parte, iar acum avem nevoie de 1, 2, 3,
4, 5, 6, 7, 8, 9 bile de stres, și o rundă de aplauze pentru
tipii ăștia, dacă am putea.
Bine făcut.
>> [Aplauze]
>> SPEAKER 1: În regulă.
Și s-ar putea păstra piesele de hârtie amintiri.
>> În regulă, deci, ai încredere în mine este o foarte mult mai ușor să treci prin asta cu
oameni decât este cu codul actual.
Dar ceea ce veți găsi într-o clipă acum, este același - Oh, vă mulțumesc.
Multumesc -
este că veți găsi că aceleași date structura, o lista inlantuita, poate de fapt,
fi utilizat ca o componentă a chiar mai mult structuri de date sofisticate.
>> Și dau seama prea tema aici este că am absolut introdus mai mult
complexitate în aplicare acestui algoritm.
Inserție, și dacă am trecut prin ea, ștergere și căutare, este un pic
mai complicat decât a fost cu o matrice.
Dar am castigat un dinamism.
Am obține o structură adaptivă de date.
>> Dar, din nou, vom plăti un preț de a avea unele complexitate suplimentară, atât în
punerea sa în aplicare.
Și suntem renunțat acces aleator.
Și pentru a fi sincer, nu e ceva frumos curat diapozitiv pot să vă dau că
spune aici este de ce o lista inlantuita este mai mult decât un tablou.
Și lăsați-l la asta.
Deoarece tema reapariția acum, chiar cu atât mai mult în următoarele săptămâni, este
că nu e neapărat un răspuns corect.
>> Acesta este motivul pentru care am axa separat de proiectare pentru seturi de probleme.
Acesta va fi foarte sensibil la context dacă doriți să utilizați aceste date
structură sau să rețină, și se va depinde de ceea ce conteaza pentru tine din punct de vedere
de resurse și complexitate.
>> Dar permiteți-mi să propun ca datele ideale structura, Sfântul Graal, ar fi
ceva care este constanta de timp, indiferent de cât de multe lucruri este
în interiorul acestuia, nu ar fi extraordinar dacă o Structura de date a revenit răspunsuri în
constanta de timp.
Da.
Acest cuvânt este în dicționar ta imens.
Sau nu, acest cuvânt nu este.
Sau orice astfel de problemă acolo.
Ei bine, să vedem dacă nu putem cel puțin ia un pas spre asta.
>> Permiteți-mi să propun o nouă structură de date care pot fi folosite pentru lucruri diferite,
în acest caz numit o tabela de dispersie.
Și așa suntem de fapt, înapoi la uite la o matrice, în acest caz, și
oarecum arbitrar, am desenat asta tabelul hash ca un tablou cu un fel de
tablou bidimensional -
sau mai degrabă este descris aici ca un doi matrice dimensionale - dar aceasta este doar
o matrice de dimensiune 26, astfel că, dacă ne sunați la masa matrice, suport de masă
Zero este dreptunghi în partea de sus.
Tabelul suport 25 este dreptunghi în partea de jos.
Și acest lucru este modul în care s-ar putea trage de date structura în care doresc să stocheze
oamenilor nume.
>> Deci, de exemplu, și nu voi trage totul aici, pe deasupra, dacă am
a avut această matrice, pe care am acum de gând să apela un tabel hash, iar acest lucru este din nou
locație zero.
Acest lucru aici este locație unul, și așa mai departe.
Eu susțin că vreau să utilizeze aceste date structura, de dragul discuției,
pentru a stoca nume de persoane, Alice și Bob și Charlie și alte nume, cum.
Deci, cred că de asta acum ca inceputurile de, să zicem, un dicționar
cu o mulțime de cuvinte.
Se întâmplă să fie numele în exemplul nostru aici.
Și acest lucru este prea Germane, probabil, la implementarea unui corector ortografic, așa cum am
s-ar putea ca problema stabilit șase.
>> Deci, dacă avem o serie de mărimea totală 26 astfel că aceasta este locația 25
în partea de jos, și eu susțin că Alice este primul cuvânt în dicționarul de
nume pe care vreau să insera în memoria RAM, în această structură de date, în cazul în care sunt
instincte care vă spune că Alice Numele ar trebui să meargă în acest tablou?
>> Avem 26 de opțiuni.
În cazul în care vrem să-i dea?
Ne-o doresc în paranteză la zero, nu?
O pentru Alice, sa-i spunem că la zero.
Și B va fi una, și C va fi de două.
Așa că am de gând să scrie Numele lui Alice aici.
Dacă vom introduce apoi Bob, sa Numele va merge aici.
Charlie va merge aici.
Și așa mai departe în jos, prin această structură de date.
>> Aceasta este o structură de date minunat.
De ce?
Ei bine, ceea ce este timpul de funcționare a introducerea numelui unui om în această
structura de date acum?
Având în vedere că acest tabel este pusă în aplicare, într-adevăr, ca o matrice.
Ei bine, e timpul constanta.
Este ordin de unul.
De ce?
>> Ei bine, cum a face tu a determina unde Alice aparține?
Te uiți la care scrisoarea de numele ei?
Primul.
Și poți ajunge acolo, dacă e un șir, de doar uita la șir
suport zero.
Deci, caracterul zero din șir.
Asta e ușor.
Am făcut asta în cripto Acum săptămâni de atribuire.
Și apoi, o dată ce știi că e Alice scrisoare este de capital o, putem scădea
pe 65 sau capitalul A sine, care ne dă zero.
Deci, noi stim acum ca Alice aparține la locația zero.
>> Și dat un pointer la aceste date structura, de un anumit fel, cât timp nu
mi iau pentru a găsi locația zero, într-o matrice?
Doar un singur pas, chiar e constanta de timp cauza acces aleator ne
propus a fost o caracteristică a unei matrice.
Deci, pe scurt, imaginind ce indicele de numele lui Alice este, care este, în
acest caz, este un, sau să rezolve doar care la zero, în cazul în care B este unul și C este
doi, imaginind că în este constanta de timp.
Trebuie doar să te uiți la prima scrisoare, imaginind în cazul zero, este un
matrice este, de asemenea, de timp constant.
Deci, punct de vedere tehnic, care este ca doi pași acum.
Dar asta e tot constant.
Deci, noi numim asta Big O de unul, așa că am inserat Alice în acest tabel în
constanta de timp.
>> Dar, desigur, eu fiind naiv aici, nu?
Ce se întâmplă dacă există un Aaron în clasă?
Sau Alicia?
Sau orice alte nume începând cu A. În cazul în care vom pune
acea persoana, nu?
Adică, acum există doar trei oamenii de pe masa, asa ca poate ne
ar trebui să pună Aaron la locație zero, unu, doi, trei.
>> Dreapta, am putea pune o aici.
Dar apoi, în cazul în care vom încerca să introduceți David în această listă, în cazul în care se merge pe David?
Acum, sistemul nostru începe de rupere jos, dreapta?
Pentru că acum David se termină aici dacă Aaron este, de fapt aici.
Iar acum ideea asta de a avea un Structura de date curat, care ne dă
inserții constantă de timp nu mai este constanta de timp, pentru că trebuie să
verifica, oh, la dracu, e cineva deja în locul lui Alice.
>> Permiteți-mi sonda restul acestor date structură, în căutarea unui loc de a pune
cineva ca numele lui Aaron.
Și astfel încât prea începe să ia timp liniar.
Mai mult decât atât, atunci când doriți să găsiți Aaron în această structură de date, și tu
verifica, și numele lui Aaron nu este aici.
În mod ideal, ar spune doar lui Aaron nu în structura de date.
Dar dacă ai face începe a face loc pentru Aaron unde ar fi fost un D
sau un E, tu, cel mai rău caz, trebuie să verificați structura de date întreg, în
caz în care revine în ceva liniar în dimensiunea tabelului.
>> Deci în regulă, voi rezolva aceasta.
Problema aici este că am avut 26 elemente în această matrice.
Lasă-mă să-l schimbe.
Hopa.
Lasă-mă să-l schimbe, astfel ca, mai degraba fiind de dimensiune 26 în total, observa în partea de jos
indicele se va schimba la n minus 1.
Dacă 26 este în mod clar prea mic pentru om " nume, pentru că există mii de
numele din lume, hai să facem doar în 100 sau 1000 sau 10000.
Să aloce doar o mult mai mult spațiu.
>> Bine că nu scade în mod necesar probabilitatea că nu vom avea două
oameni cu nume începând cu A, și Deci, ai de gând să încerce să pună un
nume de la locație la zero încă.
Ei încă de gând să se ciocnesc, care înseamnă că avem nevoie de o soluție pentru a pune
Alice și Aaron și Alicia și alte Nume care încep cu A în altă parte.
Dar cât de mult de o problema este aceasta?
Care este probabilitatea ca au coliziunilor de date
structura ca aceasta?
>> Ei bine, lasa-ma sa - vom reveni la această întrebare aici.
Si uita-te la cum am putea rezolve mai întâi.
Lasă-mă să trageți în sus această propunere aici.
Ceea ce am descris este un algoritm, o euristică numit liniar
sondare în care, dacă ați încercat să introduceți ceva aici, în aceste date
structura, care se numește o tabela de dispersie, și nu e loc acolo, te
sonda cu adevărat structura de date verificarea, este aceasta disponibilă?
Este aceasta, este disponibil acest disponibilă?
Este aceasta disponibilă?
Și când în cele din urmă este, de a introduce numele pe care ați intenționat inițial
în altă parte la acea locație.
Dar, în cel mai rău caz, singurul loc ar putea fi foarte jos a datelor
structura, la capăt de matrice.
>> Deci liniar sondare, în cel mai rău caz, decurge într-un algoritm liniar unde
Aaron, dacă se întâmplă să fie introdusă trecut în această structură de date, el ar putea
ciocnesc cu aceasta prima locatie, dar apoi termina de ghinion la sfârșitul.
Deci, acest lucru nu este o constantă timp Sfântul Graal pentru noi.
Această abordare a elementelor introduce în o structură de date numită o distribuire
tabel nu pare să fie constantă de timp cel puțin nu în cazul general.
Se poate revin în ceva liniar.
>> Deci, dacă am rezolva coliziuni oarecum diferit?
Deci, aici este o mult mai sofisticat abordare a ceea ce e mai
numit un tabel hash.
Și de hash, ca o paranteza, ceea ce Vreau să spun este indicele care
Am menționat mai devreme.
Pentru ceva hash poate fi gândit ca un verb.
>> Deci, dacă hash Alice e un nume, o funcție hash, ca să spunem așa,
ar trebui să returneze un număr.
În acest caz este zero în cazul în care ea aparține la locație de zero, unul în cazul în care ea aparține la
locație, și așa mai departe.
Deci funcția mea de hash a fost până acum super-simplu, doar uita la
Prima literă din numele cuiva.
Dar o funcție hash are ca intrare unele bucata de date, o
string, un întreg, indiferent de.
Și-l scuipă de obicei un număr.
Și că numărul este în cazul în care datele Elementul aparține într-o structură de date
cunoscut aici ca un tabel hash.
>> Deci, doar intuitiv, acesta este un ușor diferită context.
Aceasta este, de fapt se referă la un exemplu care implică de naștere, în cazul în care
ar putea fi la fel de multe ca 31 zile din luna.
Dar ce această persoană decide să face în cazul unei coliziuni?
Contextul fiind acum nu, o coliziune de nume, ci o coliziune de nastere,
În cazul în care două persoane au aceeași zi de naștere pe 2 octombrie, de exemplu.
>> STUDENT: [inaudibil].
>> SPEAKER 1: Da, așa că aici avem pârghie de liste legate.
Deci, se pare un pic diferit decât l-am desenat mai devreme.
Dar noi par să aibă la o serie pe partea stângă.
Asta e un index, pentru nici o motiv special.
Dar este încă un tablou.
Este o serie de indicii.
Și fiecare dintre aceste elemente, fiecare dintre aceste cercuri sau oblice - slash
reprezentând nul - fiecare dintre acestea indicii se pare că indică spre
ce structura de date?
O listă legat.
>> Deci, acum avem capacitatea de a Codul greu în programul nostru de
dimensiunea tabelului.
În acest caz, știm că nu e niciodată mai mult de 31 de zile într-o lună.
Atât de greu de codificare o valoare ca 31 este rezonabile în acest context.
În contextul de nume, greu de codificare 26 nu este nerezonabil-l oamenilor
nume încep numai cu, de exemplu, alfabetul implică o prin Z.
>> Putem ghiftui-le pe toate în care datele Structura atât timp cât, atunci când avem o
coliziune, nu punem numele aici, noi în loc ca aceste celule
nu ca șiruri înșiși, ci ca indicii pentru, de exemplu, Alice.
Și apoi Alice poate avea un alt indicator la un alt nume care începe cu
A. Și Bob merge de fapt aici.
>> Și dacă există un alt nume de pornire cu B, se sfârșește aici.
Și astfel fiecare dintre elementele acestui tabel cu două, dacă ne conceput acest o
ceva mai inteligent -
haide -
dacă am conceput aceasta un pic mai mult inteligent, acum devine o de date adaptive
structură, în cazul în care nu există o limită greu pe cât de multe elemente puteți introduce
în ea pentru că dacă nu au o coliziune, asta e bine.
Doar mergeți mai departe și adăugați-l la ceea ce am văzut un pic în urmă a fost
cunoscut ca o listă legată.
>> Ei bine, să ne oprim pentru un moment.
Care este probabilitatea unei coliziuni în primul rând?
Dreapta, poate eu sunt peste gândesc, poate Sunt mai mult de inginerie această problemă,
pentru că știi ce?
Da, eu pot veni cu arbitrară exemple de pe partea de sus a capului meu, cum ar fi
Allison și Aaron, dar, în realitate, dat o distribuție uniformă a
intrări, care este un inserții aleatoare într-o structură de date, ceea ce este cu adevărat
probabilitatea unei coliziuni?
Ei bine, se dovedește, de fapt foarte mare.
Lasă-mă să generalizeze această Problema este ca aceasta.
>> Deci, într-o cameră de n CS50 elevi, ceea ce este probabilitatea ca cel puțin
doi studenți în cameră au aceeași zi de naștere?
Deci, nu e ceea ce. un Hund câteva -
200, 300 de oameni aici și mai multe sute de oameni de la domiciliu de azi.
Deci, dacă ai vrut să ne întrebăm ce este probabilitatea de două persoane
în această cameră care au aceeași zi de naștere, ne putem da seama asta.
Și eu pretind de fapt, există două oameni cu aceeași zi de naștere.
>> De exemplu, nu oricine are ziua de nastere astazi?
Ieri?
Mâine?
Bine, asa ca se simte ca și cum am de gând să aibă de a face acest lucru 363 sau cam asa ceva mai mult
ori să dau de fapt de dacă avem o coliziune.
Sau am putea face doar acest lucru matematic mai degrabă decât plictisitor
face acest lucru.
Și propune următoarele.
>> Deci, eu propun ca am putea modela probabilitatea de două persoane care au
aceeași zi de naștere ca probabilitatea de 1 minus probabilitatea de nimeni având
aceeași zi de naștere.
Deci, pentru a obține acest lucru, iar aceasta este doar mod fantezist de a scrie acest lucru, pentru
Prima persoană în cameră, el sau ea poate avea oricare dintre posibil
Zile de nastere presupunând 365 zile în an, cu scuze pentru persoanele cu
Data nasterii 29 februarie.
>> Deci, prima persoană din această cameră este liber pentru a avea orice număr de zile de naștere
din cele 365 de posibilități, astfel încât Vom face asta 365 împărțit la 365,
care este unul.
Următoarea persoană în cameră, dacă scopul este de a evita o coliziune, poate doar
au ziua lui sau a ei cu privire la modul multe zile diferite posibile?
364.
Deci, al doilea termen în această expresie este face în esență, că matematica pentru noi
scăzând off o zi posibil.
Și apoi a doua zi, a doua zi, doua zi până la numărul total
de persoane în cameră.
>> Și dacă apoi ne gândim, ce este atunci probabilitatea nu de toată lumea avea
Zile de nastere unice, dar din nou 1 minus că, ceea ce avem este o expresie
care poate fi foarte fancifully arata ca aceasta.
Dar este mult mai interesant să se uite la vizual.
Aceasta este o diagramă care pe axa x este numărul de persoane în cameră,
numărul de zile de naștere.
Pe axa y este probabilitatea de o coliziune, două persoane
având aceeași zi de naștere.
>> Și Takeaway din această curbă este că de îndată ce ajungi să-ți placă 40
elevi, te-ai trezit la o probabilitate de 90% combinatorically de două
sau mai multe persoane care au aceeași zi de naștere.
Și odată ce ajungi să-ți placă 58 de persoane este aproape 100% din o șansă două
persoane în cameră vor avea aceeași zi de naștere, chiar dacă există
365 sau 366 de găleți posibile, și doar 58 persoane in camera.
Doar statistic, esti probabil pentru a obține coliziuni, care în scurt
motivează această discuție.
Asta chiar dacă avem de lux aici, și începe cu aceste lanțuri, suntem încă
va avea coliziuni.
>> Astfel că duce la intrebarea, ce este costul de a face inserări și ștergeri
într-o structură de date ca asta?
Ei bine, lasă-mă să propun -
și lasă-mă să mă întorc la ecranul peste aici - dacă ne-am n elemente în
lista, deci, dacă încercăm să introduceți n elemente, și avem
câte totalul găleți?
Să zicem 31 Total găleți în caz de naștere.
Care este lungimea maximă a unui din aceste lanțuri potențial?
>> În cazul în care din nou nu e posibil 31 Zile de nastere într-o lună.
Și noi suntem doar agregare toată lumea -
de fapt asta e un exemplu prost.
Să facem 26 în loc.
Deci, dacă au de fapt oameni ale căror nume începe cu A la Z, oferind astfel
ne 26 de posibilități.
Și suntem folosind o structura de date ca cel pe care tocmai am văzut, prin care ne-am
o serie de indicii, fiecare dintre acestea indică o listă înlănțuită unde
Prima listă este toată lumea cu numele de Alice.
A doua listă este fiecare cu nume care începe cu A, incepand
cu B, și așa mai departe.
>> Care este lungimea probabil de fiecare dintre aceste liste dacă presupunem un frumos curat
distribuirea de nume de la A la Z întreaga structură de date întreg?
Există n oameni din structura de date împărțit la 26, în cazul în care acestea sunt frumos
răspândit peste tot structură de date.
Deci lungimea fiecăreia dintre aceste lanțurilor este n împărțit la 26.
Dar în O notație mare, ce e asta?
Ce este că într-adevăr?
Deci, este într-adevăr doar n, nu?
Pentru că am spus în trecut, care uf vă împărțiți de 26.
Da, în realitate, este mai rapid.
Dar, în teorie, nu este fundamental toate că mai repede.
>> Deci, noi nu par a fi tot atât de mult mai aproape de aceasta Sfântul Graal.
De fapt, aceasta este doar timpul liniar.
La naiba, la acest moment, de ce nu ne folosesc doar o listă uriașă legat?
De ce nu am folosi doar un singur mare matrice pentru a stoca numele de
toată lumea din cameră?
Ei bine, există încă ceva convingatoare despre un tabel hash?
Există încă ceva convingătoare despre o structură de date
care arata ca aceasta?
Acest lucru.
>> STUDENT: [inaudibil].
>> SPEAKER 1: Corect, și din nou, în cazul în care este doar un algoritm de timp liniar, și un
structura de date timp liniar, de ce nu am stoca doar numele tuturor într-o mare
matrice, sau într-o listă mare legat?
Și nu mai face CS atât de mult mai greu decât aceasta trebuie să fie?
Ce este convingătoare despre acest lucru, chiar deși l-am zgâriat afară?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Inserturi nu sunt?
Mai scump.
Deci, insertii potențial ar putea încă să fie constantă de timp, chiar dacă datele
Structura arata ca aceasta, o serie de indicii, fiecare dintre care este îndreptat la
eventual o listă înlănțuită.
Cum ai putut obține constant introducerea timpul de nume?
Stick-l în față, dreapta?
>> Dacă ne sacrificăm un obiectiv de proiectare de la mai devreme, în cazul în care ne-am dorit să păstreze
numele tuturor, de exemplu, sortate, sau toate numerele de pe scena sortate,
să presupunem că avem o nesortate lista legat.
Ea doar ne costă una sau două trepte, ca în cazul lui Ben și Brian
mai devreme, pentru a insera un element la la începutul listei.
Deci, dacă nu ne pasă de sortare toate dintre numele care încep cu A sau toate
nume încep cu litera B, putem încă realiza introducerea constanta de timp.
Acum în căutarea de până Alice sau Bob sau orice nume mai general, este încă ce?
E mare de O n împărțit la 26, în cazul ideal în care toată lumea este uniform
distribuite, în cazul în care nu există la fel de multe lui A cum există lui Z, care este probabil
nerealiste.
Dar care este încă liniar.
>> Dar aici, ne întoarcem la punctul de de notație asimptotice a fi
teoretic adevărat.
Dar în lumea reală, dacă eu pretind că Programul meu poate face ceva de 26 de ori
mai rapid decât al tău, al căror program de ai de gând să preferați să utilizați?
A ta sau a mea, care este de 26 ori mai rapid?
Realist, persoana a cărei este 26 ori mai rapid, chiar dacă teoretic
algoritmi noastre rula în același asimptotic timp de funcționare.
>> Permiteți-mi propune un alt soluție cu totul.
Și dacă acest lucru nu sufla mintea ta, nu mai avem structuri de date.
Deci, acest lucru este un trie -
un fel de nume stupid.
Ea vine de la extragerilor, iar cuvântul este scris trie, t-r-i-e, din cauza
Preluare curs sună ca trie.
Dar asta e istorie a trie cuvântului.
>> Deci, un trie este într-adevăr un fel de copac, și este, de asemenea, un joc pe acel cuvânt.
Și, chiar dacă nu pot vedea destul de cu această vizualizare, un trie este un
arbore structurat, ca un arbore genealogic cu un strămoș în partea de sus și o mulțime
de nepoti si stranepoti ca frunzele de pe jos.
Dar fiecare nod într-un trie este un tablou.
Și este într-o matrice - și hai să simplifica prea mult pentru un moment - este un
matrice, în acest caz, de mărimea 26, în cazul în care fiecare nod din nou, este o matrice de dimensiune
26, în cazul în care elementul de grad zero în acel matrice reprezintă O, iar ultimul
Elementul în fiecare astfel de matrice reprezintă Z.
>> Așa că propun, atunci, că aceste date Structura, cunoscut ca un trie, poate fi
folosit, de asemenea, pentru a stoca cuvinte.
Am văzut acum un moment cum am putea stoca cuvinte, sau în acest caz nume, iar noi
vazut mai devreme cum putem stoca numere, dar dacă ne concentrăm pe numele sau siruri de caractere
aici, observa ceea ce e interesant.
Eu susțin că numele de Maxwell este în interiorul acestei structuri de date.
În cazul în care vrei să vezi Maxwell?
>> STUDENT: [inaudibil].
>> SPEAKER 1: La stânga.
Deci, ceea ce este interesant cu aceste date Structura este, mai degrabă decât magazin
șir M-A-X-W-E-L-L backslash la zero, toate adiacent, ceea ce fac în schimb
urmărește.
Dacă acesta este un trie ca structura de date, fiecare dintre noduri a căror este din nou o matrice,
și doriți să stocați Maxwell, mai întâi index și astfel nodul rădăcina lui, așa
de a vorbi, nodul cel mai de sus, la locație M, dreapta, așa
aproximativ în mijloc.
Și apoi de acolo, să urmați un pointer la un copil noduri, ca să spunem așa.
Deci, în sensul arborele genealogic al familiei, tu-l urmeze în jos.
Și care va conduce la un alt nod pe stânga există, care este
doar un alt tablou.
>> Și apoi, dacă doriți să stocați Maxwell, veți găsi indicatorul care reprezintă
O, care este cel de aici.
Apoi te duci la urmatorul nod.
Și observați - acesta este motivul pentru care imaginea lui un pic înșelătoare -
acest nod arata super mic.
Dar în partea dreaptă a acestei este Y și Z. Este doar autorul a trunchiat
imagine, astfel încât să de fapt vezi lucruri.
În caz contrar, această imagine ar fi extrem de mare.
Deci, acum vă indice în locația X, atunci W, apoi E, atunci L, atunci L. Atunci ce-i
această curiozitate?
>> Ei bine, dacă vom folosi acest tip de noi ia cu privire la modul de a stoca un șir într-un
structura de date, tot trebuie să în esență bifa în datele
Structura că un cuvânt se termină aici.
Cu alte cuvinte, fiecare dintre aceste noduri într-un fel trebuie să ne amintim că noi
urmată de fapt, toate aceste indicii și pleacă un pic
miez de pâine în partea de jos a acestei aici Structura a indica M-A-X-W-E-L-L este
într-adevăr, în această structură de date.
>> Deci, am putea face acest lucru, după cum urmează.
Fiecare dintre nodurile din imagine ne-am ferăstrău are o, o serie de dimensiuni 27.
Și este acum 27, pentru că în p. stabilit șase, vom da de fapt un apostrof,
astfel încât să putem avea nume ca O'Reilly și altele cu apostrofuri.
Dar, aceeași idee.
Fiecare dintre aceste elemente în puncte de matrice pentru o struct
nod, astfel încât doar un nod.
Deci, acest lucru este foarte amintește din lista noastră legate.
>> Și apoi am un Boolean, pe care voi apel cuvânt, care este doar de gând să fi
adevărat dacă un cuvânt se termină la acest nod din arbore.
Aceasta reprezintă efectiv mic triunghi am văzut acum o clipă.
Deci, dacă un cuvânt se termină la acel nod în copac, că domeniul cuvânt va fi adevărat,
care este conceptual verificarea off, sau suntem desen acestui triunghi, da acolo
este un cuvânt aici.
>> Deci, acesta este un trie.
Și acum întrebarea este, ce este de timp de funcționare?
Este Big O de n?
Este altceva?
Ei bine, dacă ați n nume în aceste date structura, Maxwell fiind doar unul dintre
ei, ceea ce este timpul de funcționare a introducerea sau găsirea Maxwell?
Care este timpul de funcționare de inserarea Maxwell?
Dacă există alte nume n deja în tabel?
Da?
>> STUDENT: [inaudibil].
>> SPEAKER 1: Da, e lungimea de nume, nu?
Deci M-a-x-w-e-l-l, astfel se simte ca aceasta Algoritmul este Big O de șapte.
Acum, desigur, numele va varia în lungime.
Poate e un nume scurt.
Poate e un nume mai lung.
Dar ceea ce este esențial aici este că este un număr constant.
Și poate că nu e chiar constantă, Dar Dumnezeu, în cazul în care realist, într-o
dicționar, există probabil unele limite privind numărul de litere într-un
Numele persoanei într-o anumită țară.
>> Și deci putem presupune că Valoarea este o constantă.
Nu știu ce este.
Este, probabil, mai mare decât credem ca este.
Pentru că există întotdeauna un colț caz cu un nume nebun lung.
Deci, haideți să-l k numesc, dar este încă un constantă probabil, pentru că fiecare
nume în lume, cel puțin într-o țară special, este faptul că lungimea sau
mai scurte, deci este constant.
Dar când am spus ceva este mare O, de o valoare constantă, ce-i asta
într-adevăr echivalente?
Asta e într-adevăr același lucru ar fi spus constanta de timp.
>> Acum suntem un fel de înșelăciune, nu?
Suntem un fel de pârghie unor teorii aici să spun că bine, ordinea de K este
Chiar dispune doar de un singur, și este constanta de timp.
Dar de fapt este.
Pentru că perspectiva cheie aici este că dacă ne-am n nume deja în această
structura de date, si vom introduce Maxwell, este cantitatea de timp ne duce la
introduceți Maxwell la toate afectate de cât de multe alte persoane
sunt în structura de date?
Nu par a fi.
Dacă am avut un miliard de mai multe elemente de la această trie, și apoi introduceți Maxwell, este
el la toate afectate?
Nu.
Și că este, spre deosebire de oricare dintre datele de zi Structurile am văzut până acum, în cazul în care
timpul de rulare a algoritmului este complet independent de cât de mult
lucruri este sau nu este deja în care structura de date.
>> Și astfel, cu aceasta oferă acum este un oportunitate pentru p set de șase, care va
din nou implica implementarea propriu corector ortografic, citind în 150.000
cuvinte, cum cel mai bine pentru a stoca că nu este neapărat evident.
Și, deși am aspirat pentru a găsi Sfântul Graal, eu nu fac
susțin că un trie este.
De fapt, un tabel hash ar putea foarte bine se dovedesc a fi mult mai eficient.
Dar acestea sunt doar -
care este doar una dintre deciziile de design va trebui să facă.
>> Dar, in incheiere sa ia 50 sau cam asa ceva secunde pentru a lua o privire la ceea ce se află
înainte de săptămâna viitoare și dincolo de noi tranziție din această linie de comandă
lume, dacă programe C la lucruri web bazat și limbi, cum ar fi PHP și
JavaScript și internet în sine, protocoale cum ar fi HTTP, pe care le-ați
luate pentru a acordat de ani acum, și în format text cele mai multe fiecare
zi, poate, sau văzut.
Și vom începe să coaja înapoi straturi de ceea ce este pe internet.
Și ceea ce este codul care sta la baza instrumente de astăzi.
Deci, 50 secunde ale acestui teaser aici.
Eu vă dau Warriors of Net.
>> [Redare video]
>> -A venit cu un mesaj.
Cu un protocol de toate propria sa.
El a venit la o lume de firewall-uri crude, routere nepăsătoare, și pericolele departe
mai rău decât moartea.
E rapid.
E puternic.
E TCPIP.
Si are adresa dvs..
Warriors a fileului.
>> [END redare video]
>> SPEAKER 1: Acesta este modul în care internetul va lucra ca de saptamana viitoare.