[Powered by Google Translate] [Săptămâna 6, Continuare]
[David J. Malan] [Universitatea Harvard]
[Acest lucru este CS50.] [CS50.TV]
Acest lucru este CS50 și acesta este sfârșitul săptămânii 6.
Deci CS50x, unul dintre primele cursuri la Harvard implicate în inițiativa EDX
într-adevăr, a debutat acest trecut luni.
Dacă doriți să obțineți o bucatica din ceea ce alții pe Internet
sunt acum în urma, împreună cu, vă puteți îndrepta spre x.cs50.net.
Asta vă va redirecționa la locul potrivit pe edx.org,
care a fost în cazul în care acest lucru și alte cursuri de la MIT si Berkeley acum live.
Va trebui să vă înscrieți pentru un cont, veți găsi că materialul este în mare parte același
ca ai avut acest semestru, deși cu câteva săptămâni întârziate, după cum am obține totul gata.
Dar ceea ce elevii din CS50x vor vedea acum este o interfata destul ca aceasta.
Acest lucru, de exemplu, este lider Zamyla walkthrough pentru set de probleme 0.
La conectarea la edx.org, un student CS50x vede felul de lucruri
v-ați aștepta să vedeți într-un curs: curs de luni,
prelegere pentru miercuri, pantaloni scurți diverse, de seturi de probleme, walkthroughs, PDF-uri.
În plus, după cum puteți vedea aici, masina de traduceri
de transcrieri engleză în chineză, japoneză, spaniolă, italiană,
și o grămadă de alte limbi, care va fi cu siguranță imperfectă
așa cum le implementeze în mod programatic folosind ceva numit un API,
sau interfață de programare aplicație, de la Google
care ne permite să convertească din engleză în alte limbi.
Dar, datorită minunatul spirit al unor voluntari sute de plus,
oamenii aleatorii de pe Internet, care au oferit cu amabilitate să se implice
în acest proiect, vom fi îmbunătățirea treptată a calității acestor traduceri
de oameni care au corecteze greșelile pe care calculatoarele noastre au făcut.
>> Deci, se dovedește ne-am câțiva elevi mai arată pe luni decât ne-am așteptat inițial.
De fapt, acum CS50x are 100.000 de oameni în urma de-a lungul la domiciliu.
Deci, dai seama ca sunt toate parte din această clasă de inaugurare a face acest curs în informatică
educație, în general, mai mult, în sens mai larg, accesibil.
Și realitatea este acum, cu unele dintre aceste cursuri on-line masive,
ei încep toate cu aceste numere foarte mari, așa cum se pare că am făcut aici.
Dar obiectiv, în cele din urmă, pentru CS50x este adevărat pentru a obține cât mai multe persoane pentru a linia de sosire cat posibil.
Prin design, CS50x va fi oferit de acest trecut luni
tot drumul prin 15 aprilie 2013, astfel încât oamenii care au angajamente de școală în altă parte,
locul de muncă, familia, alte conflicte și cum ar fi, au o flexibilitate un pic mai mult
cu care să se scufunde în acest curs, care, este suficient să spunem,
este destul de ambițios face numai în cazul în care pe parcursul a doar trei luni în timpul unui semestru obișnuită.
Dar acești studenți vor fi abordarea aceleași seturi problema, vizualizarea același conținut,
au acces la pantaloni scurți și aceleași similare.
Deci dau seama că suntem cu toții într-adevăr în asta împreună.
Și unul dintre obiectivele finale ale CS50x nu este doar de a obține cât mai multe oameni
la linia de sosire și să le dea această înțelegere dobandita de informatică
si programare, dar, de asemenea, să le aibă această experiență împărtășită.
Una dintre caracteristicile definitorii ale 50 din campus, sperăm,
a fost acest tip de experiență comunale, pentru o mai bună sau mai rău pentru, uneori,
dar având în acești oameni să apeleze la stânga la dreapta și de la,
și ore de birou și Hackathon și echitabil.
E un pic mai greu pentru a face acest lucru în persoană cu oameni on-line,
dar CS50x va încheia în aprilie cu prima CS50 Expo,
care va fi o adaptare on-line de ideea noastră de târg
în cazul în care aceste mii de studenți vor fi invitați să prezinte o 1 - la 2 minute de video,
fie un screencast a proiectului lor final sau videoclip le ondularea salut
și vorbesc despre proiectul lor si demoing-l,
la fel ca predecesorii tăi au făcut aici, în campus în târg,
astfel încât, până la sfârșitul semestrului lui, speranța este de a avea o expoziție la nivel mondial
de proiecte ale studenților CS50x "finale, la fel ca ceea ce vă așteaptă în luna decembrie a acestui aici, în campus.
Deci, mai mult pe faptul că, în lunile ce vor urma.
>> Cu 100.000 de studenți, însă, vine o nevoie pentru un AC câteva mai multe.
Având în vedere faptul că voi fac pârtie aici și luând CS50
câteva săptămâni înainte de lansarea acestui material de la oameni pe EDX,
realiza ne-ar plăcea să implice cât mai mulți dintre studenții noștri proprii, astfel cum este posibil în această inițiativă,
atât în ​​timpul semestrului, precum și în această iarnă și acest venirea primăverii.
Deci, dacă doriți să se implice în CS50x,
în special aderarea la CS50x pe Discuss, versiunea EDX a CS50 Discuss,
pe care mulți dintre voi ați fost utilizați în campus, avizier on-line,
vă rugăm să faceți cap la acea adresă URL, să ne spui cine ești,
pentru că ne-ar plăcea să construiască o echipă de studenți și a personalului și de facultate, cât
în campus, care sunt pur și simplu joc de-a lungul și ajutând.
Și când văd o întrebare la care e familiar pentru ei,
auzi un student de raportare unele bug undeva acolo într-o țară pe internet,
și că sună un clopot, deoarece ai avut de asemenea, că aceeași problemă
în sala de dvs. d-ceva timp în urmă, sperăm, le puteti interveni în și împărtăși propria experiență.
Deci, vă rugăm să ia parte, dacă doriți.
>> Cursuri de informatică de la Harvard au un pic de o tradiție,
CS50 printre ei, de a avea unele îmbrăcăminte, niște haine, pe care le puteți purta cu mândrie
la sfârșitul semestrului, spunând destul de mândrie că ai terminat CS50
și a luat CS50 și cum ar fi, și vom încerca mereu să implice elevii
în acest proces cât mai mult posibil, prin care vă invităm,
în jurul valorii de acest timp de semestru, studenții să-și prezinte proiectele
folosind Photoshop, sau orice instrument de alegerea pe care doriți să o utilizați
dacă ești un designer, să prezinte modele de T-shirt și jachete
și umbrele și bandane mici pentru câini avem acum și place.
Și totul este apoi - castigatorii in fiecare an sunt apoi expuse
pe site-ul cursului de la store.cs50.net.
Totul este vândut la cost acolo, dar site-ul în sine funcționează doar
și permite oamenilor de a alege culori si modele pe care le plac.
Așa că m-am gândit parts doar câteva dintre desenele de anul trecut
care au fost pe site-ul pe langa asta aici, care este o tradiție anuală.
"În fiecare zi mă SEG Faultn" a fost unul dintre cele prezentate anul trecut,
care este încă disponibilă acolo pentru absolventi.
Am avut aceasta ", CS50, Infiintata 1989."
Unul dintre Bowdens noastre, Rob, a fost foarte popular de anul trecut.
"Echipa Bowden" sa născut, acest design a fost prezentată, printre vanzatori de top.
Așa cum a fost cel de aici. Mulți oameni au avut "Febra Bowden", în conformitate cu jurnalele de vânzări.
Seama că ar putea fi acum design-ul acolo, pe internet.
Mai multe detalii despre aceasta in urmatoarea problema seturi să vină.
>> Un instrument mai: ai avut ceva de expunere și, sperăm, acum
ceva experienta hands-on cu GDB,
care este, desigur, un depanator și vă permite să manipuleze
programul tau la un nivel destul de scăzut, faci ce fel de lucruri?
Ce înseamnă GDB lasa sa faci?
Da? Dă-mi ceva. [Răspuns Student, neinteligibil]
Bine. Pas în funcție, astfel încât nu trebuie doar să tastați rula
și au lovitură programul prin toate elementele sale, imprimarea lucruri la ieșirea standard.
Mai degrabă, aveți posibilitatea să pas prin ea linie cu linie, fie tastând următoarea
pentru a merge linie cu linie cu linie sau pas să se scufunde într-o funcție, de obicei, una care ai scris.
Ce altceva GDB lasa sa faci? Da? [Răspuns Student, neinteligibil]
Imprima variabile. Deci, dacă vrei să faci un pic de introspecție în interiorul programului
fără a fi nevoie să recurgă la scrierea declarațiile printf peste tot locul,
puteți imprima doar o variabilă sau să afișeze o variabilă.
Ce altceva se poate face cu un program de depanare ca GDB?
[Răspuns Student, neinteligibil]
Exact. Puteți seta puncte de întrerupere, se poate spune executarea pauză
la funcția de principal sau funcția foo.
Se poate spune executarea pauza la linia 123.
Valorile critice și reprezintă o tehnică foarte puternic
pentru că, dacă aveți un sentiment general de unde problema ta
probabil este, nu trebuie să pierdeți timp pas cu pas prin toate elementele programului.
Puteți sări în esență, chiar acolo și apoi începeți să tastați -
intensificarea prin ea cu pas sau următoare sau similar.
Dar captura cu așa ceva GDB este că vă ajută, umană,
găsi problemele tale și pentru a găsi bug-uri dumneavoastră.
Aceasta nu găsiți neapărat le atât de mult pentru tine.
>> Deci, am introdus style50 altă zi, care este un instrument de linie de comandă scurt
care încearcă să stiliza codul tau un pic mai curat decât tine, om, ar putea avea de făcut.
Dar că, de asemenea, este de fapt doar un lucru estetic.
Dar se pare că nu e alt instrument numit Valgrind, care este un pic mai mult pentru a utiliza arcane.
Producția sa este cumplit de criptic la prima vedere.
Dar e minunat util, mai ales acum ca suntem la o parte din termenul de
în cazul în care începi să utilizați malloc și alocarea dinamică a memoriei.
Lucrurile pot merge foarte, foarte greșit repede.
Pentru că dacă vă uitați pentru a elibera memoria, sau ai ceva dereference indicatorul NULL,
sau ai ceva dereference indicatorul de gunoi, ceea ce este de obicei simptomul că rezultatele?
Seg vina. Și veți obține acest fișier de bază de un numar de kiloocteți sau megaocteți
care reprezintă starea memoriei program dumneavoastră atunci când sa prăbușit,
dar în cele din urmă programul SEG defecte, eroare de segmentare,
ceea ce înseamnă ceva rău sa întâmplat aproape întotdeauna legate de
pentru o greșeală de memorie legate de faptul că ai făcut undeva.
Deci, Valgrind vă ajută să găsiți lucruri de genul asta.
Este un instrument pe care îl executați, cum ar fi PIB, după ce ați compilat programul tău,
ci, mai degrabă decât a rula programul direct, aveți o Valgrind
și tu treci să-l program, la fel cum ai face cu GDB.
Acum, de utilizare, pentru a obține cel mai bun fel de iesire,
este un pic cam lung, astfel încât chiar acolo deasupra ecranului de care vă veți vedea Valgrind-v.
"-V" aproape universal înseamnă detaliat când sunteți folosind programele de pe un computer Linux.
Deci, aceasta înseamnă scuipa mai multe date decât s-ar putea în mod implicit.
"- Scurgere-check = plin." Acest lucru este pur și simplu spune de selectare pentru toate posibile scurgeri de memorie,
greșelile pe care am putea-au făcut. Acest lucru, de asemenea, este o paradigmă comună cu programe Linux.
În general, în cazul în care aveți un argument linie de comandă care este un "comutator",
care ar trebui sa schimbe comportamentul programului, și este o singură literă,
e-V, dar în cazul în care este pornit, doar prin designul programator,
este un cuvânt plin sau o serie de cuvinte, argumentul linia de comanda începe cu -.
Acestea sunt doar convenții omenești, dar le vei vedea din ce în ce.
Și apoi, în cele din urmă, "a.out" este nume arbitrar pentru program în acest exemplu particular.
Și aici e ceva de ieșire reprezentative.
>> Înainte de a ne uităm la ceea ce ar putea însemna că, lasă-mă să merg pe la un fragment de cod aici.
Și lasă-mă să mute asta din drum, în curând,
și haideți să aruncăm o privire la memory.c, care este acest exemplu scurt aici.
Deci, în acest program, permiteți-mi să mări cu privire la funcțiile și întrebări.
Avem o funcție principală, care apelează o funcție, f,
și apoi ce face f procedează pentru a face, în limba engleză ușor tehnic?
Ce face f proceda să fac?
Cum despre Voi începe cu linia 20, și locul stelei nu contează,
dar voi fi doar în concordanță aici cu ultima prelegere.
Ce e linia 20 nu pentru noi? Pe partea stângă. Ne vom rupe în jos în continuare.
Int * x: Ce face asta?
Bine. Este declarare un pointer, iar acum sa fie chiar mai tehnic.
Ce înseamnă, foarte concret, să declare un pointer? Altcineva?
Da? [Răspuns Student, neinteligibil] Prea departe.
Deci, sunteți de lectură pe partea dreaptă a semnului egal.
Să ne concentrăm doar pe partea stângă, doar pe int * x.
Aceasta se "declară" un pointer, dar acum hai să se arunca cu capul în mai profundă a acestei definiții.
Ce înseamnă asta concret, punct de vedere tehnic înseamnă? Da?
[Răspuns Student, neinteligibil]
Bine. Acesta se pregătește pentru a salva o adresă în memorie.
Bine. Și să ia acest pas mai departe, se declara o variabila, x, asta e 32 de biți.
Și știu că e pe 32 de biți, deoarece -?
Nu e pentru ca este un int, pentru că este un pointer în acest caz.
Coincidență faptul că este una și aceeași cu o int,
dar faptul că e steaua nu înseamnă acest lucru este un pointer
și în aparat, ca și în multe calculatoare, dar nu toate, pointerii sunt 32 de biți.
Pe hardware-ul modern, mai mult ca cele mai recente Mac-uri, cele mai recente PC-uri, este posibil să aveți 64-bit pointeri,
dar în aparat, aceste lucruri sunt 32 de biți.
Deci, vom standardiza pe asta. Mai concret, povestea merge, după cum urmează:
Noi "declară" un pointer; ce înseamnă asta?
Ne pregătim pentru a stoca o adresă de memorie.
Ce înseamnă asta?
Vom crea un variabila x zisul care preia 32 de biți
care va stoca în curând adresa un număr întreg.
Și asta e, probabil, la fel de precisă ca putem obtine.
E bine avansează pentru a simplifica lume și spun doar declară un pointer numit x.
Declară un pointer, dar dau seama și să înțeleagă ce se întâmplă de fapt pe
chiar și în doar câteva acele caractere.
>> Acum, asta e aproape un pic mai ușor, chiar dacă este o expresie mai mult.
Deci, ce este acest sens, care este evidențiat acum: "malloc (10 * sizeof (int));" Da?
[Răspuns Student, neinteligibil]
Bine. Și am să-l duc acolo. E o bucată alocarea de memorie pentru zece numere întregi.
Și acum să intrăm puțin mai adânc în; este alocarea unui segment de memorie pentru zece numere întregi.
Ceea ce este malloc se întoarce apoi?
Adresa de faptul că bucata, sau, mai concret, adresa primul octet din bucată.
Cum sunt eu atunci, programator, să știe unde se termină că bucata de memorie?
Știu că e contiguu. Malloc, prin definiție, vă va da o bucată de memorie contiguă.
Nu există lacune în ea. Aveți acces la fiecare octet în bucată,
spate în spate în spate, dar cum nu știu unde la sfârșitul acestui segment de memorie este?
Când utilizați malloc? [Răspuns Student, neinteligibil] Bine.
Tu nu faci. Trebuie să vă amintiți.
Trebuie să ne amintim că am folosit valoarea 10, iar eu nu par chiar să fi făcut asta aici.
Dar sarcina este în întregime pe mine. Strlen, care am devenit ușor bazeaza pe pentru siruri de caractere,
functioneaza doar din cauza acestei convenții de a avea \ 0
sau acest caracter special Nul, NUL, la sfârșitul unui șir.
Asta nu deține doar pentru bucăți arbitrare de memorie.
E la latitudinea dumitale. Deci linia 20, apoi, alocă o bucată de memorie
care poate stoca zece numere întregi, și îl stochează adresa primul octet
de faptul că segment de memorie în variabila x sunat.
Ergo, care este un pointer. Deci linia 21, din păcate, a fost o greșeală.
Dar, mai întâi, ceea ce o face? Se spune magazin la locația 10, 0 indexate,
de segment de memorie numite x valoarea 0.
>> Deci, observați o serie de lucruri se întâmplă.
Chiar dacă x este un pointer, amintesc de la câteva săptămâni în urmă
pe care le puteți utiliza în continuare matrice de tip notație suport pătrat.
Pentru că asta e de fapt scurt-mână notație pentru aritmetică indicatorul mai criptic-aspect.
în cazul în care ne-ar face ceva de genul asta: Ia adresa x, mutați peste 10 locuri,
apoi du-te acolo la orice adresă este stocată în acea locație.
Dar sincer, aceasta este doar atroce de a citi și a obține confortabil cu.
Deci, lumea folosește de obicei între paranteze drepte doar pentru că este atât de mult mai uman-friendly pentru a citi.
Dar asta e ceea ce se întâmplă cu adevărat sub capota;
x este o adresă, nu o matrice, în sine.
Deci, acest lucru este stocarea 0 la 10 în locația x.
De ce este acest rau? Da?
[Răspuns Student, neinteligibil] Exact.
Am alocat doar zece Ints, dar ne bazam de la 0 la programarea în C,
astfel încât să aveți acces la 0 1 2 3 4 5 6 7 8 9, dar nu 10.
Deci, fie programul este de gând să vina segmentul sau nu este.
Dar noi nu știm cu adevărat, aceasta este un fel de un comportament nedeterminist.
Este într-adevăr depinde de faptul dacă vom avea noroc.
Dacă se dovedește că sistemul de operare nu se supără dacă am folosi că octet suplimentar,
chiar dacă nu le-a dat la mine, programul meu nu s-ar putea prăbuși.
E crud, e buggy, dar ar putea să nu vezi că simptom,
sau s-ar putea vedea doar o singură dată într-un timp.
Dar realitatea este ca bug-ul este, de fapt, nu există.
Și e foarte problematic dacă ați scris un program pe care doriți să fie corecte,
pe care le-am vândut programul pe care oamenii folosesc ca de fiecare dată într-un timp eroare
pentru că, desigur, acest lucru nu este bun. De fapt, dacă aveți un telefon Android sau un iPhone
și vă descărca aplicații în aceste zile, în cazul în care v-ați avut vreodată o aplicație renunta,
toate dintr-o dată el dispare, asta e aproape întotdeauna rezultatul unor problema de memorie legate de,
prin care programatorul stricat și dereferenced un pointer
că el sau ea nu ar trebui să aibă, și rezultatul de iOS sau Android este de a ucide doar programul complet
mai degrabă decât un comportament nedefinit de risc sau un fel de compromis de securitate.
>> Nu e un bug în altă acest program în afară de asta.
Ce altceva am stricat în acest program?
Eu nu am practicat ceea ce am predicat. Da?
[Răspuns Student, neinteligibil] Bine.
Nu am eliberat de memorie. Deci, regula de degetul mare acum
trebuie să fie oricând te sun malloc, trebuie să apelați gratuit, atunci când ați terminat utilizarea acestei memorie.
Acum, când aș vrea să eliberez această memorie?
Probabil, presupunând că aceasta prima linie a fost actualizată, aș vrea să o fac aici.
Pentru că nu am putut, de exemplu, o fac aici. De ce?
Doar afara domeniului de aplicare. Deci, chiar dacă vorbim despre pointeri,
aceasta este o săptămână 2 sau 3 cauză, în cazul în care x este numai în domeniul de aplicare interiorul acolade în cazul în care acesta a fost declarat.
Deci, cu siguranta ai nu se poate elibera de acolo. Singura mea sansa de a se elibera este de aproximativ după linia 21.
Acesta este un program destul de simplu, că a fost destul de ușor, odată ce fel de înfășurat mintea ta
în jurul valorii de ceea ce face programul, în cazul în care greșelile au fost.
Și chiar dacă nu l-am vazut la prima, să sperăm că e un pic evident acum
că aceste greșeli sunt destul de ușor de rezolvat și ușor de făcut.
Dar atunci când un program este mai mult de 12 de linii lungi, e 50 de linii lungi, 100 de linii de lung,
de mers pe jos prin linia codul de linie, gândindu prin ea logic,
este posibil, dar nu deosebit de distractiv de a face, în mod constant în căutarea de bug-uri,
și este, de asemenea, dificil de a face, si asta e motivul pentru care un instrument ca Valgrind există.
Lasă-mă să mergeți mai departe și face acest lucru: să-mi deschid fereastra mea terminale,
și nu mă lăsa să ruleze doar de memorie, pentru ca memoria pare să fie bine.
Primesc norocos. Mergând la faptul că octet suplimentare la sfârșitul matrice
nu pare să fie prea problematice.
Dar lasă-mă să, cu toate acestea, face o verificare bun-simț, ceea ce înseamnă doar pentru a verifica
indiferent dacă aceasta este sau nu de fapt corectă.
>> Deci, hai sa facem Valgrind-V - scurgeri de check-= complet,
și apoi numele programului în acest caz este de memorie nu, a.out.
Așa că lasă-mă să mergeți mai departe și de a face acest lucru. Apăsați Enter.
Dragă Dumnezeu. Acest lucru este producția, iar acest lucru este ceea ce am făcut aluzie la mai devreme.
Dar, în cazul în care veți învăța să citiți prin toate prostii aici,
cea mai mare parte acest lucru este doar de ieșire de diagnosticare, care nu e interesant.
Ceea ce ochiul tău vrea cu adevărat să fie căutați este orice mențiune de eroare sau este nevalid.
Cuvinte care sugereaza probleme.
Și într-adevăr, să vedem ce se întâmplă greșit aici.
Am un rezumat de un anumit fel, "în uz la ieșire: 40. Bytes in 1 blocuri"
Nu sunt sigur ce este un bloc este încă, dar 40 octeți
de fapt, se simte ca și cum am putut da seama de unde vine de la faptul că.
40 bytes. De ce sunt de 40 octeți în uz la ieșire?
Și, mai precis, dacă vom derula în jos aici,
de ce am pierdut cu siguranta 40 octeți? Da?
[Răspuns Student, neinteligibil] Perfect. Da, exact.
Au fost zece numere întregi, și fiecare dintre acestea este dimensiunea de 4, sau 32 biți,
așa că am pierdut exact 40 bytes, deoarece, așa cum a propus, nu am sunat gratuit.
Asta e un bug, și acum să ne uităm în jos un pic mai departe și să vedem de lângă acest lucru,
"Invalid scriu de marimea 4." Acum, ce e asta?
Această adresă este exprimat ceea ce notația de bază, aparent?
Acest lucru este hexazecimal, și de fiecare dată când vedeți un număr, începând cu 0x,
inseamna hexazecimal, pe care am făcut drumul înapoi în, cred, PSET 0 a lui secțiunea de întrebări,
care a fost doar pentru a face un exercițiu de warmup, conversie zecimal în hexazecimal în binar și așa mai departe.
Hexadecimal, doar prin convenție umană, este de obicei folosit pentru a reprezenta indicii
sau, mai general, se adresează. E doar o convenție,
deoarece este un pic mai ușor de citit, e un pic mai compact decat ceva de genul zecimal,
și binar este inutil pentru majoritatea oamenilor de a utiliza.
Deci, acum, ce înseamnă? Ei bine, se pare ca exista o scriere nevalidă
de marimea 4 pe linia 21 din memory.c.
Așa că hai să ne întoarcem la linia 21, și într-adevăr, aici este faptul că de scriere nevalid.
Deci, Valgrind nu este de gând să dețină complet mâna mea și să-mi spui ce este fix,
dar este detectarea că eu fac o scriere nevalid.
Mă ating 4 octeți că nu ar trebui să fie, și se pare că asta e cauza,
cum ați subliniat, fac [10] în loc de [9] maximal
sau [0] sau ceva în între.
Cu Valgrind, dau seama de fiecare dată când scrii acum un program de
care utilizează indicii și folosește memoria, și malloc mai precis,
cu siguranta a intra în obiceiul de a gestiona acest timp
dar foarte ușor de copiat și inserat comanda Valgrind
pentru a vedea dacă există unele erori acolo.
Și o să fie copleșitoare de fiecare dată când vezi ieșire,
ci doar prin analiza vizual toată producția și a vedea dacă vezi menționează de erori
sau avertismente sau este invalid sau pierdere.
Orice cuvinte care sună ca ti-ai pus undeva.
Deci dau seama că e un instrument nou în setul de instrumente dumneavoastră.
>> Acum, pe luni, am avut o grămadă de oameni vin aici
și reprezintă noțiunea de listă legată.
Și am introdus lista de legat ca o soluție la ceea ce problema?
Da? [Răspuns Student, neinteligibil] Bine.
Matricele nu poate avea memoria adăugată pentru ei.
Dacă ați aloca o matrice de marimea 10, asta e tot ce ai.
Puteti apela o funcție ca realloc dacă te-a sunat inițial malloc,
și care poate încerca să crească matrice în cazul în care nu există spațiu spre sfârșitul anului acesta
că nimeni altcineva nu foloseste, iar daca nu e, se va găsi doar tu o bucată mai mare în altă parte.
Dar apoi se va copia toate aceste octeți în matrice nou.
Aceasta pare a fi o soluție foarte corect.
De ce este acest neatractiv?
Vreau să spun că funcționează, oamenii s-au rezolvat această problemă.
De ce am nevoie pentru a rezolva aceasta, luni, cu liste legate? Da?
[Răspuns Student, neinteligibil] Aceasta ar putea lua o lungă perioadă de timp.
De fapt, de fiecare dată când suni malloc sau realloc sau calloc, care este încă una,
orice moment, programul, vorbesc la sistemul de operare,
aveți tendința de a încetini programul de jos.
Și dacă faci aceste tipuri de lucruri în bucle, te încetinirea lucruri cu adevărat în jos.
Tu nu vei observa acest lucru pentru mai simplă a "Hello World" programe de tip,
dar în programe mult mai mari, solicitând sistemul de operare din nou și din nou, pentru memorie
sau dându-i înapoi din nou și din nou tinde să nu fie un lucru bun.
În plus, e doar un fel de intelectual - este o pierdere de timp.
De ce aloca mai multă memorie și mai mult, riscul de copierea totul în matrice noua,
dacă aveți o alternativă care vă permite să aloce memorie doar la fel de mult ca tine de fapt nevoie?
Deci, nu e plusuri și minusuri de aici.
Unul dintre plusurile acum este că avem dinamism.
Nu contează în cazul în care bucăți de memorie sunt că sunt liberi,
Eu pot sorta doar de a crea aceste pesmet prin pointeri
sa string lista mea toată legate împreună.
Dar am plăti cel puțin un preț.
>> Ce trebuie să renunțe la obținerea listelor legate?
Da? [Răspuns Student, neinteligibil] Bine.
Ai nevoie de mai multă memorie. Acum am nevoie de spațiu pentru aceste indicii,
și, în cazul acestei liste simplu super-legată
care este doar încearcă să stocheze întregi, care sunt de 4 octeți, ne tot spun
Ei bine, un indicator este de 4 octeți, așa că acum am literalmente dublat
cantitatea de memorie am nevoie doar pentru a stoca această listă.
Dar, din nou, acest lucru este un compromis constant în informatică
între timp și spațiu și, efortul de dezvoltare și alte resurse.
Ce este un alt dezavantaj de a folosi o listă legată? Da?
[Răspuns Student, neinteligibil]
Bine. Nu la fel de ușor de accesat. Noi nu mai poate pârghie
Săptămâna 0 principii ca dezbina si cucereste.
Și, mai precis, căutare binară. Deoarece, chiar dacă noi, oamenii,
poate vedea în cazul în care aproximativ mijlocul acestei liste este,
calculatorul știe doar că această listă legată pornește de la adresa numit primul.
Și asta e 0x123 sau ceva de genul asta.
Și singura modalitate programul poate găsi elementul din mijloc
este de a căuta, de fapt intreaga lista.
Și chiar și atunci, pur și simplu trebuie să caute intreaga lista, deoarece
chiar odată ce ajunge elementul din mijloc urmând indicii,
te, programul, nu au nici o idee cât de mult această listă este, potențial,
până când te-a lovit la sfârșitul anului acesta, si de unde stii programare
că ești la capătul unei liste legate?
E un pointer NULL specială, astfel încât, din nou, o convenție.
Mai degrabă decât utiliza acest indicator, am cu siguranță nu vreau să fie o valoare gunoi
îndreptat pe scena undeva, vrem să fie o parte în jos, NULL,
astfel încât să avem această terminus în această structură de date, astfel știm unde se termină.
>> Ce se întâmplă dacă vrem să manipuleze acest lucru?
Am făcut cea mai mare a acestui punct de vedere vizual, și cu oamenii,
dar ce se întâmplă dacă vrem să facem o introducere?
Deci, lista inițială a fost de 9, 17, 20, 22, 29, 34.
Ce se întâmplă dacă am vrut să apoi spațiu malloc pentru numărul de 55 de ani, un nod pentru ea,
și apoi vrem să inserați 55 în lista la fel cum am făcut-o luni?
Cum facem acest lucru? Ei bine, Anita a venit și ea a mers în esență, lista.
Ea a început de la primul element, apoi următoarea, urmatoarea, urmatoarea, urmatoarea, urmatoarea.
În cele din urmă a lovit din stânga tot drumul în jos
si realizat oh, asta este NULL. Deci, ce manipulare indicatorul necesar să fie făcut?
Persoana care a fost pe final, numarul 34, este necesar mâna stângă ridicată
la punctul de la 55, 55 nevoie de brațul stâng îndreptat în jos pentru a fi noul NULL terminator. Adoptată.
Destul de ușor pentru a insera 55 într-o listă sortată.
Și cum ar putea arăta asta?
>> Lasă-mă să mergeți mai departe și să se deschidă unele exemplu de cod aici.
Voi deschide gedit, și lasă-mă să deschid două fișiere primul.
Unul este list1.h, și permiteți-mi să reamintesc doar că aceasta a fost bucată de cod
pe care am folosit pentru a reprezenta un nod.
Un nod are atât un int n numit și un indicator numit în continuare că doar punctele de lucru următoare în listă.
Care este acum într-un fișier. H.. De ce?
E această convenție, și nu am profitat de aceasta o sumă uriașă noi înșine,
dar persoana care a scris funcțiile printf și alte
a dat ca un cadou pentru lumea toate aceste funcții prin scrierea unui fișier numit stdio.h.
Și apoi există string.h, iar apoi e map.h, și există toate aceste fișiere h
pe care le-ar putea fi văzut sau utilizate în timpul termenului scrise de alte persoane.
De obicei, în aceste fișiere sunt h. Singurele lucruri cum ar fi typedefs
sau declarații de tipuri personalizate sau declarații de constante.
Tu nu pune implementari funcții "în fișiere antet.
Ai pus, în schimb, doar prototipuri lor.
Ai pus lucrurile pe care doriți să le partajați cu lumea ceea ce au nevoie
, în scopul de a compila codul lor. Deci, doar pentru a intra în acest obicei,
ne-am decis să facem același lucru. Nu e mult, în list1.h,
dar am pus ceva care ar putea fi de interes pentru oameni din lume
care doresc să utilizeze implementarea lista noastră de legat.
Acum, în list1.c, nu voi trece prin toată chestia asta
pentru ca e un pic cam lung, acest program, dar să rulați-l reala rapid la prompt.
Lasă-mă să compileze List1, permiteți-mi să executați, apoi List1, și ceea ce veți vedea este
am simulat am un program simplu pic aici
care este de gând să-mi permite să adăugați și să eliminați numere într-o listă.
Așa că lasă-mă să mergeți mai departe și tastați 3 pentru 3 opțiunea de meniu.
Vreau să inserați numărul de - hai sa facem primul număr, care a fost de 9,
si acum am spus că lista este acum 9.
Lasă-mă să mergeți mai departe și face o altă inserție, așa că am lovit opțiunea de meniu 3.
Ce număr vreau să inserați? 17.
Enter. Și eu voi face doar una mai mult.
Lasă-mă să introduceți numărul 22.
Deci avem începuturile lista legate de faptul că am avut în format de slide-o clipă în urmă.
Cum se intampla de fapt această inserție?
Într-adevăr, 22 este acum la sfârșitul listei.
Deci, i-am spus povestea pe scena de luni și reșapate chiar acum
trebuie să fie, de fapt se intampla in cod.
Să aruncăm o privire. Lasă-mă să defilați în jos în acest dosar.
Vom treacă peste unele din functiile,
dar vom merge în jos la, să zicem, funcția de inserare.
>> Să vedem cum merge despre introducerea unui nou nod în această listă legată.
În cazul în care este declarată listă? Ei bine, hai să parcurgeți tot drumul până în partea de sus,
și observați că lista mea de legat este în esență, a declarat ca un indicator unic, care e initial NULL.
Deci, eu sunt, folosind o variabilă globală aici, care, în general, le-am predicat împotriva
deoarece face codul un pic murdar pentru a menține,
e un fel de leneș, de obicei, dar nu e leneș și nu e greșit și nu e rău
dacă scopul programului tău de limbă de mare în viață este de a simula o listă legat.
Care este exact ceea ce facem.
Deci, mai degrabă decât să constate acest lucru în principal și apoi trebuie să-l treacă la orice funcție
am scris în acest program, în loc să ne dăm seama oh, hai sa facem doar la nivel mondial
deoarece întregul scop al acestui program este de a demonstra unul și numai o singură listă legată.
Așa că se simte bine. Aici sunt prototipuri mele, și nu va trece prin toate acestea,
dar am scris o funcție de ștergere, o funcție găsi, o funcție de inserare, și o funcție de traverse.
Dar haideți să mergem acum înapoi la funcția de inserare
și a vedea modul în care aceasta funcționează aici.
Inserare este pe linia - aici vom merge.
Inserare. Asa ca nu ia nici un argument, pentru că vom cere
interiorul utilizare a acestei funcții pentru numărul care doriți să îl inserați.
Dar, mai întâi, ne pregătim pentru a le da ceva spatiu.
Aceasta este un fel de copy si paste din alt exemplu.
În acest caz, am fost alocarea unui int, de data aceasta vom aloca un nod.
Nu-mi amintesc cu adevărat cât de multe bytes-un nod este, dar asta e bine.
Sizeof poate da seama de asta pentru mine.
Și de ce sunt eu de verificare pentru NULL în linie 120?
Ce ar putea merge prost în linie 119? Da?
[Răspuns Student, neinteligibil]
Bine. Doar ar putea fi cazul în care l-am cerut prea multă memorie
sau ceva nu e în regulă și sistemul de operare nu are suficiente bytes să-mi dea,
așa că semnalează cât mai mult prin returnarea NULL, iar dacă nu verifica faptul că
și am orbește proceda pentru a utiliza adresa întors, ar putea fi NULL.
Ar putea fi o valoare necunoscută, nu este un lucru bun dacă nu -
de fapt, nu va fi o valoare necunoscută. Ar putea fi NULL, deci nu vreau
să abuzeze de ea și de risc dereferencing-l.
În cazul în care se întâmplă, mă întorc doar și vom preface ca și cum nu am primit inapoi nici de memorie, la toate.
>> În caz contrar, spun utilizatorul să-mi dai un număr pentru a insera, eu numesc GetInt vechiul nostru prieten,
și apoi aceasta a fost noua sintaxă am introdus pe luni.
"Newptr-> n" înseamnă să ia adresa care va fost dat de malloc
care reprezintă primul octet al unui obiect nou nod,
și apoi du-te la câmp denumit nr.
O mică întrebare trivia: Acesta este echivalent cu ceea ce linie de cod criptic mai mult?
Cum altfel aș fi putut fi scris asta? Vrei să ia o lovitură de cuțit?
[Răspuns Student, neinteligibil]
Bine. Utilizarea nr., Dar nu e la fel de simplu ca asta.
Ce am mai întâi trebuie să fac? [Răspuns Student, neinteligibil]
Bine. Am nevoie pentru a face * newptr.n.
Deci, acest lucru este indicatorul spune noi este evident o adresă. De ce?
Pentru că a fost returnat de malloc. * Newptr spune "du-te acolo",
și apoi odată ce ești acolo, atunci puteți folosi mai familiare. n,
dar aceasta doar pare un pic urât, mai ales în cazul în care noi, oamenii, sunt de gând să
egal indicii cu săgeți tot timpul, lumea a standardizat pe această notație săgeată,
care face exact acelasi lucru.
Astfel încât să utilizați numai -> notația atunci când lucru pe stânga este un pointer.
În caz contrar, dacă e un struct reală, utilizați nr..
Și apoi asta: De ce am inițializa newptr-> de lângă NULL?
Noi nu vrem o mână stângă marionetă off de la sfârșitul etapei.
Ne dorim ca aceasta îndreptată direct în jos, ceea ce înseamnă sfârșitul acestei liste
ar putea fi de la acest nod, așa că mai bine asigurați-vă că este NULL.
Și, în general, initializarea variabilelor sau membrii de date și structs
la ceva este doar bună practică.
Doar permițându-gunoiului există și va continua să existe, în general, te scoate din necaz
în cazul în care ați uitat să faci ceva mai târziu.
>> Iată câteva cazuri. Aceasta, din nou, este funcția de inserare,
și primul lucru pe care am verificati daca este variabilă numită în primul rând,
că variabila globală este NULL, înseamnă că nu există nici o listă legată.
Noi nu am introdus nici numere, asa ca e banal pentru a introduce acest număr curent
în listă, pentru că pur și simplu aparține la începutul listei.
Deci asta a fost atunci când Anita a fost doar stau aici singur, pretinzând
nimeni altcineva nu a fost aici pe scenă până când am alocat un nod,
atunci ea ar putea ridica mâna pentru prima dată,
în cazul în care toată lumea a venit pe scenă după ea luni.
Acum aici, aceasta este o verificare în cazul în care ceva trebuie să spun, dacă nodul nou valoarea n
este <valoarea lui n în primul nod curent,
înseamnă că există o listă care este legat început.
E cel puțin un nod în listă, dar acest nou tip
înainte de a aparține, așa că avem nevoie să se miște lucrurile în jurul valorii.
Cu alte cuvinte, în cazul în care lista a început doar cu, să zicem,
doar numărul 17, care e - de fapt, putem face acest lucru mai clar.
Dacă începem povestea noastră cu un indicator numit aici în primul rând,
și inițial este NULL, si vom introduce numarul 9,
numărul 9 în mod clar parte la începutul listei.
Așa că hai să ne prefacem că malloced doar adresa sau numărul 9 și a pus-o aici.
Dacă prima este de 9 în mod implicit, primul scenariu am discutat înseamnă doar punctul hai tipul ăsta aici,
lasă ca NULL, acum avem numărul 9.
Numărul următor dorim să introduceți este 17.
17 aparține aici, așa că vom avea de a face unele pas cu pas logic prin asta.
Asa ca hai sa schimb, inainte de a face asta, hai să pretindem că ne-am dorit pentru a introduce numărul 8.
>> Deci, doar de dragul lui comoditate, am de gând să atrag aici.
Dar tine minte, malloc poate pune cel mai oriunde.
Dar, de dragul desenului, am să-l pun aici.
Așa că am alocat prefac doar un nod pentru numărul 8, aceasta este NULL în mod implicit.
Ceea ce trebuie să se întâmple acum? Un tânăr de lucruri.
Am făcut această greșeală pe scena in data de luni în cazul în care vom completa un pointer ca aceasta,
apoi a făcut acest lucru, și apoi am susținut - am orfani oricine altcineva pe scenă.
Pentru că tu Cant - ordinea operațiunilor de aici este importantă,
pentru că acum ne-am pierdut acest nod 9, care este doar un fel de plutire în spațiu.
Deci, acest lucru nu a fost abordarea dreapta pe luni.
Mai întâi trebuie să facem altceva.
Starea lumii arata ca acest lucru. Inițial, 8 a fost alocat.
Ceea ce ar fi o modalitate mai bună de a insera 8?
În loc de actualizarea acestui indicator în primul rând, actualizat doar asta aici în loc.
Deci, avem nevoie de o linie de cod care va transforma acest personaj NULL
într-un indicator real care este îndreptat la nodul 9,
și apoi ne putem schimba în condiții de siguranță de la punctul de la prima tipul ăsta aici.
Acum avem o listă, o listă legată, din două elemente.
Și ce înseamnă acest fapt arata ca aici?
Dacă ne uităm la codul, observați că am făcut exact acest lucru.
Am spus newptr, și în această poveste, a fost îndreptat newptr la tipul ăsta.
>> Așa că lasă-mă să elaboreze un lucru mai mult, și ar trebui să au lăsat camera un pic mai mult pentru acest lucru.
Deci, iartă desen micuță.
Acest tip se numește newptr.
Aceasta este variabila am declarat câteva rânduri mai devreme, în linie - chiar deasupra 25.
Și se indică la 8. Deci, atunci când spun newptr-> urmator, asta înseamnă du-te la struct
care este indicat a fi puțin prin newptr, deci iată-ne, du-te acolo.
Atunci săgeata spune obține următorul câmp, și apoi = este pus spune ce valoare acolo?
Valoare care a fost, în primul, ceea ce a fost în valoare de primul?
În primul rând a fost îndreptat la acest nod, astfel încât înseamnă aceasta ar trebui să arate acum la acest nod.
Cu alte cuvinte, ceea ce pare chiar dacă o mizerie ridicol cu ​​scrisul meu,
ceea ce este o idee simpla de a muta doar în jurul valorii de aceste săgeți
se traduce la Codul cu doar acest liner unul.
Păstrează ceea ce este în primul următorul câmp și apoi actualizați ceea ce este de fapt prima.
Să mergem mai departe și fast-forward, prin unele dintre acestea,
si uita-te numai la această inserție coada pentru acum.
Să presupunem că am ajunge la punctul în care mi se pare că următorul câmp de unii nod este NULL.
Și la acest punct, în poveste, un detaliu pe care am atenua peste
este ca am introdus un alt indicator de până aici, în linie 142, indicatorul predecesorul.
În esență, în acest moment, în poveste, o dată lista devine lung,
Am facut un fel de nevoie să-l meargă cu două degete pentru că dacă merg prea departe,
amintesc într-o singură listă de lungime, nu poți merge înapoi.
Deci, această idee a predptr este degetul meu stâng, și newptr - nu newptr.
Un alt indicator care este aici este degetul meu altul, iar eu sunt doar un fel de mers pe jos lista.
Asta e motivul pentru care există. Dar haideți să ia în considerare doar unul dintre cazurile mai simple aici.
În cazul în care câmpul pe care indicatorul de pe lângă este NULL, ceea ce e implicație logică?
Dacă sunt dipozitive de această listă și te-a lovit un pointer nul?
Esti la sfârșitul listei, și astfel codul pentru a adăuga acest element, atunci o altă
este un fel de intuitivă, care va avea următorul nod al cărui pointer este NULL,
astfel încât acesta este în prezent NULL, si schimba-l, totuși, să fie adresa de nod nou.
Deci, noi suntem doar desen în codul săgeata care am desenat pe scenă prin ridicarea mâna cuiva stânga.
>> Și cazul în care voi flutur mâinile puțin pentru moment,
doar pentru că cred că e ușor să te pierzi atunci când o facem în acest tip de mediu,
este de verificare pentru inserare la mijlocul lui lista.
Dar, doar intuitiv, ceea ce trebuie să se întâmple în cazul în care doriți să dau seama
în cazul în care unele număr aparține în mijloc este ca nu trebuie sa-l meargă
cu mai mult de un deget, mai mult de un pointer,
seama de unde îi aparține de verificare este elementul <cel curent,
> Curentă, și o dată ce găsiți acel loc,
atunci va trebui să faci acest tip de joc în cazul în care vă mutați coajă de indicii în jurul valorii de foarte mare atenție.
Și acest răspuns, în cazul în care doriți să motiv, prin acest lucru la domiciliu pe cont propriu,
se reduce doar la aceste două linii de cod, dar ordinea acestor linii este foarte importantă.
Pentru că dacă te las cuiva mana si ridica altcineva e în ordine greșită,
din nou, ai putea ajunge orphaning listă.
Pentru a rezuma mai mult conceptual, introducerea la coada este relativ simplă.
Inserare la cap este, de asemenea, relativ simplă,
dar trebuie să vă actualizați un indicator suplimentar de această dată
pentru a stoarce numărul 5 în lista de aici,
și apoi inserarea în mijlocul presupune un efort chiar mai mult,
la foarte atent introduce numărul 20 în locația corectă,
care este între 17 și 22.
Deci, aveți nevoie pentru a face ceva de genul avea noul nod 20 de puncte la 22,
și apoi, indicatorul care nodului trebuie să fie actualizate ultima dată?
E 17, pentru a insera de fapt.
Deci, din nou, voi amâna codul actual pentru că punerea în aplicare particular.
>> La prima vedere, e un pic coplesitor, dar este de fapt doar o buclă infinită
care este looping, looping, looping, looping, și de rupere de îndată ce te-a lovit indicatorul NULL,
moment în care se poate face inserarea necesare.
Acest lucru, atunci, este reprezentantul legată de inserare cod listă.
Asta a fost un fel de mult, si se simte ca și cum ne-am rezolvat o problemă,
dar am introdus o un întreg alta. Sincer, ne-am petrecut tot acest timp
pe mare O și Ω și timpul de funcționare, încercând să rezolve problemele mai repede,
și aici facem un pas mare înapoi, se simte.
Și totuși, dacă scopul este de a stoca date,
se simte ca Sfântul Graal, așa cum am mai spus, luni, ar fi cu adevărat
pentru a stoca lucruri instantaneu.
>> De fapt, să presupunem că am făcut lista pune deoparte pentru un moment legat
și am introdus în locul noțiunea de tabel.
Și să ne gândim doar de o masă pentru un moment ca o matrice.
Această matrice și acest caz are aici unele elemente de 26, 0 25, prin
și să presupunem că aveți nevoie de ceva bucată de depozitare pentru numele:
Alice si Bob și Charlie și cum ar fi.
Și ai nevoie de o anumită structură de date pentru a stoca aceste nume.
Ei bine, ai putea folosi ceva de genul o listă legată
și ai putea merge lista de introducerea Alice înainte de Bob și Charlie după Bob și așa mai departe.
Și, de fapt, în cazul în care doriți să vedeți codul de genul asta ca o paranteza,
știu că în list2.h, facem exact acest lucru.
Nu vom trece prin acest cod, dar aceasta este o variantă de primul exemplu
care introduce un struct parte ne-am mai văzut înainte de elev numitul,
si atunci ce este de fapt stochează în lista de legat este un pointer la o structură de elev
, mai degrabă decât un număr întreg simplu pic, nr.
Deci dai seama că e cod acolo, care implică siruri de caractere reale,
dar dacă obiectivul la îndemână într-adevăr acum este de a aborda problema eficienței,
nu ar fi frumos dacă suntem dat un obiect numit Alice,
vrem să o pună în locul potrivit într-o structură de date,
se simte ca și cum ar fi într-adevăr frumos să afișezi doar Alice,
al cărui nume începe cu A, în prima locatie.
Și Bob, al cărui nume începe cu B, în a doua locație.
Cu o matrice, sau să începem numindu-l un tabel, un tabel hash de la faptul că,
putem face exact acest lucru. Dacă ni se dă un nume ca Alice,
un șir de caractere ca Alice, unde poti sa pui un-L-i-c-e?
Avem nevoie de o hueristic. Avem nevoie de o funcție pentru a lua unele de intrare ca Alice
și să se întoarcă un răspuns, "Pune Alice în această locație."
Și această funcție, această cutie neagra, va fi numit o funcție hash.
>> O funcție hash este ceva care are o intrare, cum ar fi "Alice",
și se întoarce la tine, de obicei, locația numerică, în unele structuri de date în cazul în care Alice îi aparține.
În acest caz, funcția hash nostru ar trebui să fie relativ simplă.
Funcția hash noastră ar trebui să spun, dacă ți sa dat "Alice", pe care personajul trebuie să-mi pasă?
Primul. Așa că mă uit la [0], iar apoi spun, dacă [0] este un caracter, returna numărul 0.
Dacă e B, întoarce 1. Dacă C e, întoarce 2, și așa mai departe.
Toate index 0, și că mi-ar permite să inserați Alice si Bob, apoi, apoi Charlie și așa mai departe
în această structură de date. Dar există o problemă.
Ce se întâmplă dacă Anita vine din nou?
În cazul în care nu am pus Anita? Numele ei, de asemenea, începe cu litera A,
și se simte ca și cum am făcut-o mizerie și mai mare a acestei probleme.
Avem acum inserarea imediată, inserarea constanta de timp, într-o structură de date
, mai degrabă decât mai rău caz liniar,
dar ce putem face cu Anita în acest caz?
Care sunt cele două opțiuni, într-adevăr? Da?
[Răspuns Student, neinteligibil] Ok, deci am putea avea o altă dimensiune.
Asta e bine. Astfel încât să putem construi lucruri în 3D așa cum am vorbit despre verbal luni.
Am putea adăuga un alt acces aici, dar să presupunem că nu, am încercat să păstreze acest simplu.
Scopul întregii aici este de a avea imediat constantă timp de acces,
Deci, asta e adăugând complexitate prea mult.
Care sunt alte opțiuni atunci când încearcă să inserați Anita in aceasta structura de date? Da?
[Răspuns Student, neinteligibil] Bine. Deci, am putea muta în jos oricine altcineva,
cum ar fi Charlie ghionturi jos Bob și Alice, iar apoi am pus Anita în cazul în care ea într-adevăr vrea să fie.
>> Desigur, acum, e un efect secundar al acestei.
Această structură de date este, probabil, util nu pentru că vrem să inserați o dată pe oameni
ci pentru că vrem să verificați dacă sunt acolo mai târziu
dacă vrem să imprime toate numele din structura de date.
Am de gând să faci ceva cu aceste date în cele din urmă.
Așa că acum am un fel de filetat peste Alice, care nu mai este în cazul în care ea ar trebui sa fie.
Nici nu este Bob, și nici nu este Charlie.
Deci, poate că acest lucru nu este o idee prea bună.
Dar, într-adevăr, aceasta este o opțiune. Am putea schimba toată lumea în jos,
sau naiba, Anita a venit târziu pentru joc, de ce nu am pus doar Anita
Nu aici, nu aici, nu aici, hai să punem doar ea un pic mai jos în listă.
Dar, apoi, această problemă începe să revină din nou.
S-ar putea fi capabil de a găsi Alice instantaneu, pe baza unui nume primul ei.
Și Bob instantaneu, și Charlie. Dar apoi te uiți pentru Anita,
și vezi tu, hmm, Alice este în modul.
Ei bine, lasă-mă să verificați de mai jos Alice. Bob nu este Anita.
Charlie nu este Anita. Oh, nu există Anita.
Și dacă veți continua ca trenul de logică tot drumul,
ce e momentul cel mai rău caz de funcționare de a gasi sau de a introduce Anita în această structură de date nouă?
Este O (n), nu?
Pentru că, în cel mai rău caz, nu e Alice, Bob, Charlie. . .
tot drumul până la cineva pe nume "Y", deci nu e doar un singur loc rămas.
Din fericire, nu avem nici cea numita "Z", asa ca am pus la Anita foarte jos.
>> Nu ne-am rezolvat cu adevarat problema.
Deci, poate avem nevoie de a introduce această a treia dimensiune.
Și se pare că, dacă facem introduce această a treia dimensiune,
nu putem face acest lucru perfect, dar Sfântul Graal va fi obtinerea
constantă în timp inserarea si insertii dinamice, astfel încât
nu avem la greu-cod-o serie de dimensiune 26.
Noi putem introduce cât mai multe nume ca vrem, dar să luăm nostru de 5 minute de pauză aici
și de a face apoi că în mod corespunzător.
Bine. Am setat povestea destul de artificial acolo
prin alegerea Alice si Bob, apoi, apoi Charlie și apoi Anita,
al cărui nume a fost, evident, de gând să se ciocnesc cu Alice.
Dar întrebarea pe care am ajuns, luni, cu cat este doar probabilă este
pe care le-ar obține aceste tipuri de coliziuni? Cu alte cuvinte,
în cazul în care vom începe să utilizați această structură de tabel, care este de fapt doar o matrice,
în acest caz, de 26 de locații,
Ce se întâmplă dacă intrări noastre sunt distribuite uniform în loc?
Nu e artificial Alice si Bob și Charlie și David și așa mai departe în ordine alfabetică,
este repartizată în mod uniform de la A la Z.
>> Poate vom avea noroc si nu vom avea două O să lui sau două a lui B
cu o probabilitate foarte mare, dar ca cineva a subliniat,
dacă am generalizat această problemă și nu 0 - 25
dar, spune, 0 prin 364 sau 65, de multe ori numărul de zile într-un an tipic,
și a cerut întrebare, "Care este probabilitatea ca noi doi în această cameră au aceeași zi de naștere?"
Pune-i o altă cale, care e probabilitatea ca noi doi avem un nume începând cu A?
Un fel de întrebare este același, dar acest lucru spațiu de adrese,
acest spațiu de căutare, este mai mare în cazul aniversari,
pentru că avem atât de mult mai multe zile în an decat litere din alfabet.
Care este probabilitatea unei coliziuni?
Ei bine, ne putem gândi la acest lucru prin imaginind matematica sens opus.
Care este probabilitatea de a nu coliziuni?
Ei bine, această expresie aici, spune că ceea ce este probabilitatea
dacă există doar o singură persoană în această cameră, că au o zi de naștere unic?
E 100%. Pentru că dacă nu există decât o singură persoană în cameră,
lui sau ziua ei de naștere poate fi oricare dintre cele 365 de zile din an.
Deci, opțiunile de 365/365 dă-mi o valoare de 1.
Deci, probabilitatea în cauză, la moment este doar 1.
Dar dacă există oa doua persoană în cameră,
ce e probabilitatea ca ziua de nastere a acestora este diferit?
Nu e doar 364 zile posibile, ignorând ani bisecți,
pentru ziua lor de a nu intra în coliziune cu alte persoane.
Deci, 364/365. În cazul în care o terță persoană vine în, e 363/365, și așa mai departe.
Așa că am păstra înmulțirea acestor fracțiuni, care devin mai mici și mai mici,
să dau seama ce este probabilitatea ca toți dintre noi au aniversari unice?
Dar atunci putem, desigur, să ia doar ca răspuns și întoarceți-l în jurul valorii de
și de a face un minus toate că, o expresie vom ajunge în cele din urmă
dacă vă amintiți din spate a cărților de matematică, se pare ceva de acest fel,
care este mult mai ușor de interpretat grafic.
Și acest grafic aici are pe axa x numărul de aniversari,
sau numărul de persoane cu aniversari, și pe axa y este probabilitatea unui meci.
Și ce acest lucru este să spun este că, dacă aveți, să zicem, chiar,
hai să aleagă ceva de genul 22, 23.
Dacă e 22 sau 23 de persoane în cameră,
probabilitatea ca doi dintre acei oameni foarte puține sunt de gând să aibă aceeași zi de naștere
este de fapt super-mare, combinatorially.
50% cote că într-o clasă de doar 22 de persoane, un seminar, practic,
2 dintre aceste persoane sunt de gând să aibă aceeași zi de naștere.
Pentru că există atât de multe moduri în care puteți avea aceeași zi de naștere.
Chiar mai rău, dacă te uiți la partea dreaptă a diagramei,
de timpul pe care îl aveți o clasă cu 58 de elevi în ea,
probabilitatea de 2 persoane au ziua de nastere este mare super, super, aproape 100%.
Acum, că e un fel de fapt amuzant despre viața reală.
>> Dar implicațiile, acum, pentru structuri de date și stocare a informațiilor
înseamnă că doar presupunând că aveți un frumos, curat de distribuție, uniformă a datelor
și aveți o gamă destul de mare pentru a se potrivi o grămadă de lucruri
nu înseamnă că ai de gând să obțineți de oameni in locatii unice.
Vei avea coliziuni. Deci, această noțiune de hashing, cum e numit,
ținând seama de o intrare ca "Alice", și masaj-l într-un fel
și apoi revenind un răspuns cum ar fi 0 sau 1 sau 2.
Noțiuni de bază înapoi o parte din producția această funcție este afectat de această probabilitate de coliziune.
Deci, cum putem descurca acele coliziuni?
Ei bine, de la un caz, putem lua ideea că a fost sugerat.
Ne putem schimba doar toata lumea jos, sau poate, pur și simplu, un pic mai mult,
mai degrabă decât oricine altcineva mișcare, să mergem doar la Anita partea de jos a locului disponibil.
Deci, în cazul în care Alice este în 0, Bob este în 1, Charlie este în 2,
vom pune în locul în care Anita 3.
Și aceasta este o tehnica in structuri de date numit liniară palpare.
Liniară pentru că te plimbi doar această linie, și tu ești un fel de palpare
pentru locuri disponibile în structura de date.
Desigur, aceasta revine în O (n).
În cazul în care structura de date este într-adevăr plin, e 25 de oameni în ea deja,
și apoi Anita vine, ea se termină până la ceea ce ar fi locația Z, și asta e bine.
Ea încă se potrivește, și putem so găsim mai târziu.
>> Dar acest lucru a fost contrară obiectivului de accelerarea lucrurile.
Și ce dacă am introdus, în schimb această a treia dimensiune?
Această tehnică se numește, în general, înlănțuirea separată, sau cu lanturi.
Și ce-un tabel hash este acum, această structură de tabel,
tabelul este doar un tablou de pointeri.
Dar ceea ce aceste indicii indica este ghici ce?
O listă legate. Și ce dacă luăm cea mai bună a acestor două lumi?
Noi folosim matrice pentru indicii inițiale
în structura de date astfel încât să putem merge instantaneu de la [0] [1], [30] sau așa mai departe,
dar astfel încât să avem o oarecare flexibilitate si putem potrivi Anita și Alice și Adam
precum și orice alte Un nume,
lăsăm în schimb alte axe cresc arbitrar.
Și, în cele din urmă am, începând de luni, au capacitatea de expresiv că cu lista legat.
Putem crește o structură de date arbitrar.
Alternativ, am putea face doar un imens 2-dimensionale matrice,
dar asta va fi o situație îngrozitoare, dacă unul dintre rânduri dintr-o matrice 2-dimensional
nu este suficient de mare pentru persoana suplimentară al cărei nume se întâmplă pentru a începe cu A.
Doamne ferește, avem de a realoca un imens 2-dimensionale structura
doar pentru că există atât de mulți oameni, a numit un
mai ales atunci când există atât de puțini oameni cu numele Z ceva.
E doar de gând să fie un foarte rare structură de date.
Deci nu e perfect prin orice mijloace, dar acum avem cel puțin au capacitatea de
pentru a găsi instantaneu în cazul în care Alice sau Anita aparține,
cel puțin în ceea ce privește axa verticală,
și apoi trebuie doar să decidă în cazul în care pentru a pune Anita sau Alice în această listă legată.
Dacă nu ne pasă de sortare lucruri, cât de repede am putea introduce Alice într-o structură ca asta?
E timpul constanta. Noi indicele în [0], iar în cazul în care nu există nici o cuiva,
Alice merge la începutul acestei liste legate.
Dar asta nu e o afacere uriașă. Pentru că dacă Anita apoi vine de-a lungul
un numar de pasi mai târziu, în cazul în care nu aparține Anita?
Ei bine, [0]. OOP. Alice este deja în această listă legată.
>> Dar dacă nu ne pasă de sortare aceste nume,
ne putem muta pur și simplu peste Alice, inserați Anita, dar chiar că este constanta de timp.
Chiar daca nu e Alice și Adam și toate aceste alte nume A,
nu e într-adevăr le schimba fizic. De ce?
Pentru că am făcut aici cu lista legate, care cunoaște aceste noduri au fost oricum sunt?
Tot ce trebuie sa faci este sa treci de pesmet.
Mutare în jurul valorii de săgețile, nu trebuie să se deplaseze fizic orice date în jurul valorii de.
Deci, putem insera Anita, în acest caz, instantaneu. Constantă de timp.
Deci avem constantă timp de căutare, și constantă în timp inserarea de cineva ca Anita.
Dar un fel de a simplifica lumii.
Ce se întâmplă dacă am mai târziu doriți să găsiți Alice?
Câți pași se că va dura?
[Răspuns Student, neinteligibil]
Exact. Numărul de persoane înainte de Alice în lista de legat.
Deci, nu e destul de perfect, pentru că structura noastră de date, din nou, are acest acces pe verticală
și apoi are aceste liste linked suspendate - de fapt, să nu-l trage o matrice o.
Acesta a acestor liste legate agățat jos de pe ea, care arata ceva de genul asta.
Dar problema este dacă Alice și Adam și toate aceste alte nume A
ajung mai mult și mai mult acolo,
găsirea cineva ar putea sfârșesc prin a lua o grămadă de pași,
bcause trebuie să traverseze lista de legat,
care este o operație liniară.
Deci într-adevăr, atunci, în cele din urmă de timp inserare este O (n), unde n este numărul de elemente din listă.
Împărțit de, hai să numim aceasta arbitrar m, unde m este numărul de liste legate
pe care o avem în această axă verticală.
Cu alte cuvinte, daca ne asumam cu adevarat o distribuție uniformă de nume,
total nerealiste. Există, evident, mai mult de câteva scrisori decât altele.
>> Dar dacă presupunem, pentru moment, o distribuție uniformă,
și ne-am n totalul persoanelor, și lanțuri m totale
disponibile pentru noi, atunci durata de fiecare dintre aceste lanțuri
destul de simplu va fi totală, n împărțit la numărul de lanțuri.
Deci, N / m. Dar aici e în cazul în care putem fi cu toții matematic inteligent.
m este o constantă, pentru că există un număr fix de acestea.
Ai de gând să declare matrice la început,
și nu suntem redimensionarea axei verticale. Prin definiție, care rămâne fixat.
E doar axa orizontală, ca să spunem așa, care este schimbarea.
Deci punct de vedere tehnic, acest lucru este o constantă. Deci, acum, inserarea de timp
Este destul de mult O (n).
Așa că nu se simte tot atât de mult mai bine.
Dar ceea ce este adevărul aici? Ei bine, în tot acest timp, de săptămâni,
am spus O (n ²). O (n), 2 x N ², - n, împărțit la 2. . . ech.
E doar ² n. Dar acum, în această parte a semestrului,
putem începem să vorbim despre lumea reală din nou.
Și n / m este absolut mai rapid decât n pace.
Dacă aveți o mie de nume, și le rupe în sus, în compartimente multiple
astfel încât să aveți doar zece nume din fiecare dintre aceste lanțuri,
căutarea absolut zece lucruri va fi mai rapid decât o mie de lucruri.
Și astfel unul din seturile de probleme viitoare este de gând să vă provocare
să se gândească exact că, deși, da,
asimptotic și matematic, acest lucru este încă doar liniar,
care e de rahat, în general, atunci când încearcă să găsească lucruri.
În realitate, aceasta va fi mai rapid decât cel
din aceasta cauza divizor.
Și deci nu e din nou va fi acest compromis
și acest conflict între teorie și realitate,
și unul dintre butoanele va începe de cotitură în acest moment, în semestrul
este mai mult de realitate, o așa cum am un fel de pregătiți pentru sfârșitul lui semster,
cum vom introduce lumea de programare web,
în cazul în care într-adevăr, performanța va conta, deoarece utilizatorii sunt de gând să
începe să se simtă și să aprecieze decizii proaste de proiectare.
>> Deci, cum te duci despre punerea în aplicare a unui legat - un tabel hash cu 31 de elemente?
Și exemplul anterior a fost arbitrar despre aniversari.
Dacă cineva are o zi de naștere de la 1 ianuarie sau februarie 1, le vom pune în acest galeata.
Dacă e 02 ianuarie, 2 februarie, 2 martie, le vom pune în acest galeata.
Asta e motivul pentru care a fost de 31. Cum vă declara un tabel hash?
Ea poate fi destul de simplu, de masă * nod este numele meu arbitrar pentru aceasta, [31].
Acest lucru îmi dă 31 pointeri la noduri,
și care îmi permite să aibă 31 pointeri la preturi legate de
chiar dacă aceste lanțuri sunt inițial NULL.
Ce vreau să afișezi dacă vreau să stocați "Alice", "Bob", "Charlie"?
Ei bine, avem nevoie să-și încheie aceste lucruri într-o structură
pentru că avem nevoie de Alice la punctul lui Bob, pentru a indica Charlie, și așa mai departe.
Noi nu putem avea doar numele singur, așa că am putea crea o nouă structură numită nod aici.
>> Ce este un nod real? Ce este un nod în această listă nouă legat?
Primul lucru, numit cuvânt, este pentru numele persoanei.
LUNGIME, probabil, se referă la lungimea maximă a numelui unui om,
indiferent de faptul că este, 20, 30, 40 de caractere în cazuri de colt nebun,
și +1 este pentru ce? E doar caracterul NULL plus, \ 0.
Deci, acest nod este împachetarea "ceva" in interiorul de la sine,
dar, de asemenea, declară un pointer numit următoare
astfel încât să putem lanțul de Alice la Bob să Charlie și așa mai departe.
Poate fi NULL, dar nu trebuie neapărat să fie.
Orice întrebări cu privire la aceste tabele de dispersie? Da?
[Student cere întrebare, neinteligibil] O matrice - întrebare bună.
De ce este acest cuvânt char într-o matrice, mai degrabă decât doar char *?
În acest exemplu oarecum arbitrară, nu am vrut să aibă de a recurge
la malloc pentru fiecare dintre numele originale.
Am vrut să declare o sumă maximă de memorie pentru șirul
astfel încât am putut copia în structura Alice \ 0 și nu trebuie să se confrunte cu malloc și gratuit și similar.
Dar am putea face asta dacă aș fi vrut să fie mai conștienți de utilizarea spațiului. Bună întrebare.
Deci, haideți să încercăm să generalizeze departe de acest
și să se concentreze pe restul de astăzi, în general, mai multe structuri de date
și alte probleme pe care le pot rezolva folosind aceleași fundamente
chiar dacă structurile de date se pot diferi în datele lor.
>> Deci, se dovedește în informatică, copacii sunt foarte frecvente.
Și vă puteți gândi la un fel de copac ca un arbore genealogic,
în cazul în care există unele rădăcini, unele matriarch sau patriarh,
bunica sau bunicul sau mai devreme spate,
sub care sunt mama și tata sau frații sau diverse place.
Deci, o structură arborescentă are noduri si are copii,
de obicei 0 sau mai multe copii pentru fiecare nod.
Și unii dintre jargon pe care le vedeți în această imagine aici
este oricare dintre copiii mici sau nepoții pe marginile
care nu au săgeți care provin de la ei,
acestea sunt frunzele așa-numitele, și oricine de pe interior
este un nod interior; puteți apela acest ceva de-a lungul acestor linii.
Dar această structură este destul de comună. Asta e un pic arbitrar.
Avem un copil pe stânga, avem trei copii de pe dreapta,
doi copii de pe partea din stânga jos.
Astfel încât să putem avea diferite dimensiuni copaci, dar dacă vom începe să standardizeze lucruri,
și s-ar putea aminti acest videoclip de la Patrick în binar de căutare de pe o anterior
căutare on-line, binare nu trebuie să fie puse în aplicare cu o matrice
sau bucăți de hârtie pe o tablă.
Să presupunem că ai vrut să stocați numere intr-o structura mai sofisticată de date.
Ai putea crea un copac ca asta.
Ai putea avea un nod declarată în C, iar acel nod poate avea cel puțin două elemente în interiorul de ea.
Unul este numărul pe care doriți să stocați, iar cealaltă este - ei bine, avem nevoie de unul mai mult.
Cealaltă este copiilor săi.
Deci, aici e altă structură de date. De data aceasta, un nod este definit ca stocarea unui număr n
și apoi doi pointeri, copil stânga și dreapta copil.
Și nu sunt arbitrare. Ce este interesant despre acest copac?
>> Care e modelul în modul în care ne-am stabilit asta sau cum Patrick, aceasta este prevăzut în filme lui?
E un fel de evident că există unele sortare întâmplă pe aici,
dar ceea ce e regula simpla? Da?
[Răspuns Student, neinteligibil]
Eveniment. Dacă vă arunca o privire la acest lucru, veți vedea numerele de mici de pe partea stângă,
Numerele mari de pe partea stângă, dar asta e valabil pentru fiecare nod.
Pentru fiecare nod, copilul său din stânga mai puțin de ea, și copilul său drept mai mare decât acesta.
Ce înseamnă acest lucru este acum dacă vreau să căutați această structură de date pentru, să zicem, numărul 44,
Trebuie să înceapă de la rădăcină, pentru că așa cum, cu toate aceste structuri mai complexe de date acum,
avem doar un pointer la un singur lucru, la început.
Și în acest caz, începutul este radacina. Nu e capătul din stânga,
e rădăcina acestei structuri. Vad ca aici e 55, iar eu caut 44.
În ce direcție vreau să merg?
Ei bine, eu vreau să merg la stânga, pentru că în mod evident, la dreapta va fi prea mare.
Deci observați aici, tu ești un fel de tocare conceptual copac în jumătate
pentru că nu sunteți niciodată merge în jos pe partea dreaptă.
Așa că acum mă duc la 55 la 33. E prea mic al unui număr.
Caut 44, dar acum știu că dacă 44 este, în acest copac, pot merge, evident, la dreapta.
Deci, din nou, eu sunt tăierea copac în jumătate.
E destul de mult identice conceptual la cartea de telefon.
Este identic cu ceea ce am făcut cu lucrările de pe tablă,
dar este o structura mult mai sofisticat, care ne permite să facem efectiv
acest dezbina si cucereste prin proiectarea algoritmului,
și, de fapt, traverseaza o structura ca asta - Ups.
Traversarea unei structuri de acest fel, în cazul în care e doar "du-te acest fel sau du-te în acest fel,"
înseamnă că tot codul care îndoit mintea ta la început atunci când la punctul de punere în aplicare
sau mers pe jos prin ea acasă, pentru căutare binară, folosind recursivitate sau iterație,
este o durere în gât. Găsiți elementul din mijloc, apoi alegeți rotunjirea în sus sau în jos.
>> E o frumusete la acest lucru, deoarece putem folosi acum recursivitate din nou,
dar mult mai curat. Într-adevăr, dacă ești la numărul 55 și doriți să găsiți 44,
te duci lăsat în acest caz, atunci ce faci? Puteti rula algoritm exact același.
Ai verificat valoarea de nod, apoi te duci la stânga sau la dreapta.
Apoi, verificați valoarea nodului, du-te la stânga sau la dreapta.
Acest lucru este perfect potrivit pentru recursia.
Deci, chiar dacă, în trecut, am făcut câteva exemple destul de arbitrare care implică recursivitate
care nu au nevoie să fie recursiv, cu stuctures de date,
mai ales copaci, este o aplicare perfecta a acestei idei de a lua o problemă,
scădere el, și apoi rezolvarea același tip de, dar mai mici, programul.
>> Deci, există o altă structură de date pe care le pot introduce.
Acesta este conceput la prima vedere, să se uite criptic, dar asta e uimitor.
Deci, aceasta este o structura de date numita trie, trie, care este moștenit de la recuperarea cuvântul,
care nu se pronunță re-try-val, dar asta e ceea ce lumea numește aceste lucruri. Incearca. T-r-i-e.
Este o structură arborescentă de un anumit fel, dar fiecare dintre noduri într-un trie
pare a fi ceea ce? Și aceasta este un pic înșelătoare, pentru că e un fel de prescurtate.
Dar se pare ca fiecare nod din acest trie este de fapt o matrice.
Și chiar dacă autorul această diagramă nu le-a arătat,
în acest caz, această trie este o structura de date al cărui scop în viață este de a stoca cuvinte
cum ar fi A-L-i-c-e sau B-o-b.
Și modul în care aceste date la magazine de Alice si Bob și Charlie și Anita și așa mai departe
se foloseste o matrice prin care pentru a stoca Alice într-un trie,
vom începe de la nodul rădăcină, care arata ca o matrice,
și că a fost scrisă în notație stenografie.
Autorul a omis abcdefg, deoarece nu au nici un nume cu asta.
Ei au aratat numai M și P și T, dar în acest caz,
Să se mute departe de Alice si Bob și Charlie unor nume care sunt aici.
Maxwell este, de fapt, în această diagramă.
Deci, cum a făcut magazin autorul M-o-x-w-e-l-am?
El sau ea a început la nodul rădăcină, și sa dus la [M], deci aproximativ 13, 13, în locația matrice.
Apoi de acolo, e un pointer.
Un pointer care să conducă la o altă matrice.
De acolo autorul indexate în care matrice în locul A, astfel cum este descris acolo la stânga sus,
și atunci el sau ea a urmat un alt pointer la matrice,
și a mers la indicatorul la locatia X.
Apoi, în următoarea locație matrice W, E, L, L, și așa mai departe,
și, în sfârșit, să încercăm de fapt, de a pune o imagine la acest lucru.
Ce face un aspect nod ca în codul?
Un nod într-un trie conține o serie de indicatori către mai multe noduri.
Dar există, de asemenea, trebuie să fie un fel de valoare boolean, cel puțin în această punere în aplicare.
I se întâmplă să-l numesc is_word. De ce?
Pentru că atunci când ești introducerea Maxwell, nu ești inserarea
nimic în această structură de date.
Tu nu scrii M. Tu nu scrii X.
Tot ce faci este în urma pointeri.
Indicatorul care reprezintă M, atunci indicatorul care reprezintă o,
atunci indicatorul care reprezintă X, apoi W, E, L, L,
dar ceea ce trebuie să facă la sfârșitul este un fel de du-te, verifica, am ajuns la această locație.
Nu a fost un cuvânt care se încheie aici, în structura de date.
>> Deci, ceea ce este cu adevărat un trie umplut cu și autorul a ales să reprezinte
aceste terminuses cu triunghiuri mici.
Acest lucru înseamnă doar că faptul acestui triunghi e aici, această valoare boolean de adevărate
înseamnă că, dacă te duci înapoi în copac,
ceea ce înseamnă un cuvânt numit Maxwell este în acest sens.
Dar cuvântul foo, de exemplu,
nu este în copac, pentru că dacă am începe de la nodul rădăcină până aici, la partea de sus,
Nu e nici indicatorul f, nu indicatorul o, nu o indicatorul. Foo nu este un nume în acest dicționar.
Dar, prin contrast, Turing, T-u-r-i-n-g. Din nou, nu am păstra t sau u sau r sau I sau N sau g..
Dar am făcut-o în magazinul această structură de date o valoare de adevărata cale până aici, în acest nod - în copac
prin setarea acestei valori boolean a is_word la true.
Deci, un trie este un fel de meta acestei structuri foarte interesant,
în cazul în care nu ești într-adevăr stocarea cuvintele ei înșiși pentru acest tip de dicționar.
Pentru a fi clar, esti doar stocarea da sau nu, există un cuvânt care se termină aici.
>> Acum, ce e implicație?
Dacă aveți 150,000 cuvinte într-un dicționar care sunteți încercarea de a stoca în memorie
folosind ceva de genul o listă legată,
aveți de gând să aibă 150000 noduri în lista dvs. de legat.
Și de a găsi unul dintre aceste cuvinte ar putea lua în ordine alfabetică O (n).
Liniară de timp. Dar, în cazul aici un trie,
ceea ce este timpul de rulare a găsi un cuvânt?
Se pare că frumusețea este că, chiar dacă aveți deja 149,999 cuvinte, în acest dicționar,
puse în aplicare cu aceasta structura de date,
cât de mult timp este nevoie pentru a găsi o persoană sau inserați mai mult în faptul că, la fel ca Alice, Alice?
Ei bine, e doar 5, poate 6 pasi pentru caracter la final.
Din cauza presense de alte nume din structura
nu intra in modul de inserare Alice.
Mai mult decât atât, găsirea Alice o dată acolo sunt 150,000 cuvinte în acest dicționar
nu lua in drumul tau de a găsi Alice, la toate,
pentru ca Alice este. . . . . aici, pentru că am găsit o valoare boolean.
Și dacă nu există nici un boolean adevărat, atunci Alice nu este în această structură de date de cuvinte.
Cu alte cuvinte, timpul de rulare a găsi lucruri și inserarea lucruri în această nouă
Structura de date a trie este O a - nu e n.
Din cauza presense de 150.000 de oameni nu are nici un efect asupra Alice, se pare.
Deci, hai să spunem k, unde k este lungimea maximă a unui cuvânt în limba engleză
care este de obicei nu mai mult de 20 si ceva de caractere.
Deci, k este o constantă. Deci, Sfântul Graal se pare că am găsit acum
este faptul că de un timp trie, constanta pentru inserții, pentru căutările, pentru ștergeri.
Deoarece numărul de lucruri deja în structura,
care nu sunt chiar fizic acolo. Din nou, acestea sunt sortați doar de verificat off, da sau nu,
nu are nici un impact asupra acesteia timp de funcționare în viitor.
>> Dar nu trebuie sa fie o captură, altfel nu ne-ar fi pierdut atât de mult timp
cu privire la toate aceste structuri alte date doar pentru a ajunge în cele din urmă la un secret care este uimitor.
Deci, ce preț plătim pentru a realiza acest lucru măreția aici? Spațiu.
Acest lucru este masiv. Și motivul pentru care autorul
nu l prezinte aici, observăm că toate aceste lucruri care arata ca matrice,
el nu a trage restul de copac, restul trie,
pentru că ei nu sunt doar relevante pentru poveste.
Dar toate aceste noduri sunt super largi, și fiecare nod din arbore preia
26 sau, de fapt, ar putea fi 27 de caractere, deoarece, în acest caz, am fost, inclusiv spațiu pentru apostrof
astfel încât să putem avea cuvinte apostrophized.
În acest caz, acestea sunt tablouri mari. Deci, chiar dacă ei nu sunt picutured,
aceasta ia o cantitate masivă de memorie RAM.
Care ar putea fi bine, especilly în hardware modernă,
dar asta e compromisul. Vom ajunge mai putin timp de a petrece mai mult spațiu.
Deci, în cazul în care se întâmplă toate astea?
Ei bine, hai să facem - să vedem aici.
Să facem un salt la tipul ăsta aici.
>> Credeti sau nu, distractiv la fel de mult ca și C a fost de ceva timp acum,
suntem atingerea punctului în semestrul în care este timpul să treceți la lucruri mai moderne.
Lucrurile pe un nivel superior. Și chiar dacă pentru următoarele două săptămâni
vom continua să ne cufunda în lumea de indicii și de gestionare a memoriei
pentru a obține că mângâierea cu care putem construi apoi pe,
Jocul final este în cele din urmă să se introducă, în mod ironic, nu această limbă.
Vom petrece, cam 10 minute vorbind despre HTML.
Toate HTML este este un limbaj de marcare, și ceea ce este un limbaj de marcare
aceste serii este de paranteze deschise și închise brațe care spun că "face acest îndrăzneț"
"Face acest cursive" "face acest centrat."
Nu e tot ce intelectual interesant, dar e foarte util.
Și e cu siguranță omniprezent în aceste zile.
Dar ceea ce este puternic despre lumea de HTML, si programare web, în ​​general, mai mult,
este construirea lucruri dinamice; scrierea de cod în limbaje cum ar fi PHP sau Python sau Ruby sau Java sau C #.
Într-adevăr, indiferent de limba dvs. de alegere este, și generând HTML dinamic.
Generarea ceva numit CSS dinamic.
Cascading Style Sheets, care este, de asemenea, despre estetica.
Și astfel, chiar dacă, astăzi, dacă mă duc la unele site ca Google.com familiar,
și mă duc pentru a vizualiza, dezvoltator, sursa de vedere, pe care poate le-ați făcut înainte,
dar merge pentru a vedea sursa, chestia asta pare destul de probabil criptic.
Dar acest lucru este cod de bază care implementează Google.com.
Pe partea din fata. Și de fapt, toate acestea sunt lucruri pufoase estetica.
Acest lucru este CSS aici. Dacă am ține de defilare în jos vom obține unele chestii de culori diferite.
Acest lucru este HTML. Codul de Google arata ca un dezastru, dar dacă am deschide de fapt o altă fereastră,
putem vedea unele structuri la acest lucru.
Dacă aș deschide acest sus, observați aici, e un pic mai ușor de citit.
Vom vedea în scurt timp această etichetă, [cuvântul] este o etichetă,
HTML, cap, corp, div, script-ul, zona de text, durata, centrat, div.
Și acest lucru este, de asemenea, sorta de criptic cu aspect de la prima vedere,
dar toate mizeria asta urmeaza anumite tipare, modele și repetabile,
astfel că, odată ce vom obține elementele de bază în jos, vei fi capabil de a scrie cod ca acest
și manipula apoi cod ca acest lucru utilizând un alt limbaj, numit JavaScript.
Și JavaScript este un limbaj care rulează în interiorul unui browser
astăzi că vom folosi pe cursurile de la Harvard, pentru instrumentul de cumpărături curs care utilizează Google Maps
pentru a vă oferi o gramada de dinamism, Facebook vă oferă pentru a vedea actualizările de stare instant,
Stare de nervozitate îl folosește pentru a vă arăta tweets instantaneu.
Toate acestea vom începe să ne cufunda inch
Dar pentru a ajunge acolo, avem nevoie să înțelegem ceva despre internet.
Acest clip aici este doar un minut lung, și să presupunem pentru moment acest lucru este, de fapt,
cum Internetul funcționează ca un teaser pentru ceea ce e pe cale să vină. Eu vă dau "Warriors of Net."
>> [♫ Muzica ♫ Slow cor]
[Naratorul Barbat] El a venit cu un mesaj.
Cu un protocol de tot lui.
[♫ muzica electronica mai repede ♫]
El a venit într-o lume de firewall-uri interesante, nepăsător routere,
și pericolele mult mai rele decât moartea.
E rapid. E puternic. E TCP / IP, și el are adresa ta.
Warriors of Net.
[Malan] Săptămâna viitoare, atunci. Internetul. Programare web. Acest lucru este CS50.
[CS50.TV]