>> David J. MALAN: În regulă.
Deci, bun venit la primul vreodată Postmortem CS50 pentru un test.
Ne-am gândit să inaugurăm această tradiție în acest an.
Și aceasta va fi o oportunitate sa se plimbe prin
soluții la testul.
Și vom accelera sau încetini pe bază de în interes de cei de aici.
>> Deci, esti, probabil, aici, pentru că ești interesat de modul în care ar putea avea sau
ar fi răspuns la unele dintre aceste probleme.
Deci, de ce să nu ne aruncăm o privire în această secțiune în primul rând?
Asa ca obtinerea siruri de caractere.
Acest lucru ți-a dat trei versiuni diferite a unui program care a fost, în cele din urmă,
menirea de a obține un șir de la un utilizator.
Indiferent daca sunt sau nu a făcut-o, care a fost la stânga la tine pentru a determina.
>> Și ne-am întrebat la întrebarea 0, să presupunem că versiunea 1 este
compilat și executat.
De ce s-ar putea segfault program?
La prima vedere, orice sugestii de ce?
Da.
>> Audiența: Așa că am amintesc să fi văzut acest lucru în un exemplu anterior de a privi
char * s și de a vedea scanarea de s și văzând că este un pointer, cum
a afectat ce ai scanat in?
Este e sau adresa de e?
>> David J. MALAN: OK.
Bun.
Deci, în cele din urmă, sursa de probleme este probabil de gând să reducă
pentru că variabila s.
Și este într-adevăr o variabilă.
Tipul de date de care variabila este char *, ceea ce înseamnă că va
conține adresa unui caracter.
Și în aceasta constă înțelegere.
O să conțină adresa de un caracter sau, mai general,
adresa primului caracter în un întreg bloc de caractere.
>> Dar în care captura este că s scanare, scop în de viață, este dat o adresă și având în vedere
un cod format, cum ar fi% s, citit un șir în bucată de
memorie la acea adresa.
Dar, pentru că nu e nici un semn egal în fața că virgulă pe primul
linie de cod, pentru că noi nu facem de fapt, aloca orice memorie cu
malloc, pentru că nu a făcut de fapt aloca o serie de unele de dimensiuni, toate
ce faci este citirea utilizator tastatură de intrare în unele complet
Valoarea de gunoi, care este în s. în mod implicit.
Deci, cotele sunt ai de gând să segfault dacă că adresa nu doar așa se întâmplă
pentru a fi o valoare pe care le puteți, în fapt, scrie.
Așa de rău, nu a aloca memoria acolo.
>> Deci, respectiv 1, ne-am întrebat, să presupunem că versiunea 2 este
compilat și executat.
De ce s-ar putea segfault acest program?
Deci, aceasta este mai puțin buggy.
Și nu există într-adevăr doar un singur mod evident de unde puteți
declanșa o segfault aici.
Și acest lucru este tematic.
Orice moment folosim c în memorie, ceea ce ai putea face pentru a induce un segfault
cu versiunea 2?
>> Audiența: Dacă utilizați ca intrare în un șir care este mai mult de 49
caractere.
>> David J. MALAN: Exact.
De fiecare dată când văd ceva fix lungime atunci când vine vorba de o matrice, dvs.
radar ar trebui să meargă pe faptul că acest lucru ar putea fi problematic dacă nu sunteți verificarea
limitele de o matrice.
Și asta e problema aici.
Suntem încă utilizați scanf.
Suntem încă folosesc% s, ceea ce înseamnă că încercați pentru a citi un șir de utilizator.
Care va fi citit în s, care, în acest moment, este efectiv
adresa de o bucată de memorie sau e echivalent.
Este numele unei matrice de caractere de memorie.
>> Dar, exact că, dacă ați citit un șir care este mai mult de 49 de caractere, 49
pentru că aveți nevoie de cameră pentru backslash 0, ai de gând să se reverse
ca tampon.
Și s-ar putea avea noroc și să fie capabil să Trimite un caracter 51, 52, 53.
Dar la un moment dat, sistemul de operare este de gând să spun, nu.
Acest lucru cu siguranta nu este de memorie ai voie să atingi.
Iar programul va segfault.
>> Deci nu, euristica ar trebui să fie nici o timp ai lungime fixă, aveți
pentru a vă asigura că verificarea lungimea de ceea ce este pe care încercați
pentru a citi în ea.
>> Audiența: Deci, pentru a rezolva asta, ai putea au avut o declarație de verificare de fapt,
este cu atât mai mare lungime mult sau mai puțin?
>> David J. MALAN: Absolut.
Doar aveți o afecțiune care spune că, în cazul în care -
sau mai degrabă nu știi neapărat în avans cât de multe caractere
utilizatorul este de gând să tastați, deoarece aveți pui și ou.
Nu până când nu ați citit-o cu scanf poate îți dai seama cât de mult este.
Dar, la acel moment, e prea târziu, pentru că le-ați citit deja în
unele bloc de memorie.
Deci, ca o paranteza, a evită a bibliotecii CS50 acest aspect cu totul, retragere
prin utilizarea fgetc.
Și se citește un caracter la un moment dat, de-a lungul, știind-toeing sfat pe care le
nu se poate scurge un caracter dacă ai citit-o la un moment dat.
>> Captura este cu rechemare getstring este că trebuie să ne în mod constant re-size
că bucată de memorie, care este doar o durere.
Este o mulțime de linii de cod pentru a face asta.
Deci, o altă abordare ar fi să folosi de fapt, un văr, așa
de a vorbi, de scanf.
Exista variante de o mulțime de aceste functii care verifica de fapt,
lungime de cât de multe caractere s-ar putea citi maxim.
Și ai putea specifica, nu citesc mai mult de 50 de caractere.
Așa că ar fi o altă abordare, dar mai puțin cazarea de intrări mai mari.
>> Deci, întrebarea 2 cere, să presupunem că versiunea 3 este compilat și executat.
De ce s-ar putea segfault acest program?
Deci, aceasta este de fapt aceeași răspunde, chiar dacă aceasta
arată un pic crescator.
Folosim malloc, care se simte ca ne dăm pe noi înșine mai multe opțiuni.
Și apoi vom elibera că memorie la final.
Este încă la doar 50 de bytes de memorie.
Așa că am putea încerca în continuare să citească în 51, 52, 1000 bytes.
O să segfault pentru exact același motiv.
>> Dar există un alt motiv prea.
Ce altceva ar putea malloc întoarcere pe lângă adresa de o bucată de memorie?
Aceasta ar putea reveni nul.
Și pentru că nu suntem de verificare pentru că, am putea face ceva
prost pentru un alt motiv, care este faptul că am putea fi spune scanf, citit
intrare a utilizatorului de la tastatura 0 în locație, AKA nul.
Și că, de asemenea, va fi cu siguranta declanșa o segfault.
Deci, în scopul testul lui, ne-ar au acceptat, fie a celor ca o
motiv valabil.
Una dintre ele este identică.
Unul este un pic mai nuanțată.
>> În cele din urmă, cu privire la program utilizarea de memorie, cum versiunea 2 și
versiune 3 diferă?
Deci, pentru ceea ce merită, am văzut o aprovizionare aparent fără sfârșit de posibil
răspunsuri la acest lucru.
Și printre răspunsurile oamenilor, ceea ce am fost în speranța pentru, dar am acceptat alte
lucruri, a fost o mențiune a faptul că versiunea 2 se utilizează
așa-numitul stivă.
Versiunea 3 este folosind heap.
Și funcțional, acest lucru nu are într-adevăr face toate că de mult de o diferență.
La sfârșitul zilei, suntem încă abia 50 de bytes de memorie.
>> Dar că a fost unul dintre răspunsurile posibile că am fost cautati la.
Dar veți vedea, după ce ați primit chestionare de înapoi de la TFS, pe care am făcut
să accepte alte discuții ale acestora utilizări disparate de memorie, precum și.
Dar stiva si heap-ar fi fost un răspuns ușor pentru a merge cu.
Orice întrebări?
Vă dau Rob.
>> ROB BOWDEN: Deci problema 4.
Aceasta este cea în care a trebuit să umple în numărul de octeți din toate
aceste tipuri diferite utilizate.
Deci, primul lucru pe care îl vedem.
Să presupunem o arhitectură pe 32 de biți, ca acest aparat CS50.
Deci unul dintre lucrurile fundamentale despre Arhitecturi pe 32 de biți, care ne spune
exact cât de mare un pointer se întâmplă să fie în arhitectura.
>> Deci, imediat, știm că orice pointer tip este de 32-biți sau 4 bytes.
Deci, uita la această masă, o nod * este un tip de pointer.
Care va fi de 4 bytes.
Struct nod *, care este literalmente identic cu stele nod.
Și astfel încât va fi de 4 bytes.
Șir de caractere, asa ca nu arata ca un pointer încă, dar typedef, A
string este doar un char *, care este un tip pointer.
Astfel că va fi de 4 bytes.
>> Deci, aceste trei sunt toate cele 4 bytes.
Acum, nod și studenților sunt un pic mai complicat.
Deci, uita la nodul și elev, vom vedea nod ca un întreg și un pointer.
Si student este de două indicii în interiorul de ea.
Deci, cel puțin pentru cazul de față, modul că vom ajunge calcul pentru dimensionarea
acest struct este doar să adăugați totul care este în interiorul struct.
>> Astfel de nod, avem un întreg, care este de 4 bytes.
Avem un pointer, care este de 4 bytes.
Și astfel un nod se întâmplă pentru a prelua 8 bytes.
Și în mod similar pentru elev, avem un pointer care este 4 octeți și un alt
pointer care este de 4 bytes.
Astfel că se va termina a fi de 8 bytes.
Deci, nod și elev sunt de 8 bytes.
Și aceștia trei sunt toate cele 4 bytes.
Întrebări cu privire la asta?
Da.
>> Audiența: Este a fost un 64-bit arhitectură, ar fi că
dubla toate acestea?
>> ROB BOWDEN: Nu ar fi dubla toate dintre ele.
Deci, pe 64 de biți arhitectura, aceasta, din nou, schimbări care lucru fundamental că o
pointer este acum pe 64 de biți.
Da.
Deci, un indicator este de 8 bytes.
Deci, acestea că au fost 4 bytes vor fi de 8 bytes.
Un student, care a fost de două indicii, bine, acum o să
fi de 8 bytes, 8 bytes.
Se va face de 16 bytes.
>> Dar un nod este încă 4 bytes.
Deci, acest indicator se va să fie de 8 octeți.
Acest lucru este de 4 bytes.
Deci, un nod este doar de gând să fie de 12 bytes.
Orice alte întrebări pe care o?
Deci, cea viitoare, acestea sunt codurilor de stare HTTP.
Și a trebuit să descrie circumstanțele în care acestea ar putea
fi returnat.
o problemă pe care am auzit unii elevi au este că au încercat să facă
erori fie pe final clientului.
Deci, atunci când vom încerca să facă cererea la server, ceva nu merge
greșit la sfârșitul nostru.
Dar, în general, aceste coduri sunt fiind returnat de server.
Așa că vrem să ne dăm seama ce se întâmplă greșit sau chiar pe serverul care
cauzeaza aceste lucruri să fie returnat.
Deci, de ce s-ar putea întoarce un server de cod de stare 200?
Orice gândurile?
>> Da.
Deci, ceva despre succes cererea trecut prin.
Și acestea sunt în măsură să se întoarcă tot ce ai cerut.
Deci, totul a fost bine.
Ce zici de 302 găsit?
Da.
>> Audiența: Serverul a fost în căutarea pentru ceea ce ai cerut.
Dar nu-l poate găsi.
Deci, există o eroare.
>> ROB BOWDEN: Deci, serverul a fost în căutarea pentru ceea ce ai vrut.
Deci, sa ne uitam aici, 302 găsite, a fost capabil să-l găsească.
>> Audiența: Îmi pare rău.
A constatat înseamnă că au găsit-o.
Scuze.
>> ROB BOWDEN: Deci 302 constatată.
Serverul poate găsi ceea ce ai vrut.
>> Audiența: Dar nu e ea afișează?
>> ROB BOWDEN: Diferența dintre acest 302 si 200 este aceea că
știe ce vrei.
Dar aceasta nu este exact în cazul în care ai vrut să întreb.
Deci, 302 este o redirecționare tipic.
Deci, ați solicitat o pagină.
Ea stie, oh, vreau pentru a te întoarce acest lucru.
Dar aceasta este la un URL diferit.
Deci, hei, ce vrei de fapt acest lucru.
>> David J. MALAN: Este o piesa care a spus că am dat voi o redirecționare
funcție care utilizează funcția header care, la rândul său, imprimate localizare,
colon, iar apoi URL-ul la care pe care doriți să respingeți utilizator.
Chiar dacă nu ai văzut 302 în mod explicit acolo, că este ceea ce PHP
ar introduce magic ca antetul a spune exact ceea ce a spus Rob acolo -
găsit.
Dar du-te aici în loc.
>> ROB BOWDEN: OK.
Deci, ce zici de 403 interzis?
>> Audiența: Cred că este că serverul este, în principiu spune că clientul
nu pot accesa pagina de pornire.
>> ROB BOWDEN: Deci, da.
Ei bine, răspunsul tipic am fost asteptam ceva, cum ar fi, fișierele
Nu sunt schimbat atributele corespunzător.
Asta e, probabil, în ce condiții le-ai văzut.
Dar există un motiv pentru care clientul ar putea fi de vina aici.
Există de fapt un alt cod de stare -
401.
Deci, acestea sunt foarte asemănătoare.
>> 401 este neautorizat.
Și 403 este interzis.
Și așa neautorizat tu exclusiv te dacă nu sunteți logat
Dar logare ar putea însemna că sunteți autorizat.
Dar dacă sunteți deja conectat și tu încă nu au permisiunea, atunci
puteți obține, de asemenea, interzis.
Deci, dacă sunteți conectat și nu au permisiune, interzis este, de asemenea,
ceva ce se poate obține.
>> David J. MALAN: Și mecanismul de care aceste probleme sunt de obicei
soluționate pe server este prin ce comanda?
Chmod, dacă e, într-adevăr, o permisiuni emite pe fișierul sau directorul.
>> ROB BOWDEN: Atunci, 404 nu a fost găsit.
Da.
Deci, spre deosebire de 302 în cazul în care aceasta nu a fost exact în cazul în care ceri, dar se stie ce
vrei, aceasta, ea are doar nici o idee despre ceea ce vrei.
Și nu se solicită ceva valabil.
418 Sunt un ceainic și apoi 500 server intern.
Deci, de ce s-ar putea să obțineți asta?
>> Așa segfault -
Eu de fapt nu știu clasificarea standard pentru aceasta.
Dar, în cazul în care codul de PHP a avut ceva greșit în el, în teorie, ar putea
de fapt segfault, în care caz, acest 500 eroare de server intern, ceva
este în neregulă cu a serverului dvs. configurare.
Sau există o eroare de sintaxă în codul PHP.
Sau ceva rău se întâmplă.
>> David J. MALAN: Ne-am văzut segfault printre răspunsuri câteva oamenilor.
Și punct de vedere tehnic, s-ar putea întâmpla.
Dar că ar fi un PHP, programul scris de către alte persoane, de fapt,
segfaulted, care numai în cazul în care aceste persoane dat-o și a scris codul buggy în
interpret lor ar PHP în sine segfault.
Deci, chiar dacă 500 este ca un segfault în spirit, este aproape întotdeauna
rezultat de o problemă de fișier de configurare cu server-ul de web sau, după cum a spus Rob,
o eroare de sintaxă, ca tine nu a închis-un citat.
Sau ai pierdut un punct și virgulă pe undeva.
>> Audiența: Deci, pentru PSET charter, am că atunci când am făcut-o o dată ce am apasat
browser-ul, dar nimic nu a venit, ceea ce ei au numit pagină albă.
Dar a fost din cauza codului.
Cred că a fost JavaScript, corect?
>> ROB BOWDEN: Da.
>> Audiența: Vrei ca eroare mai veni?
>> ROB BOWDEN: Deci, nu ar fi ajuns această eroare, deoarece totul
din punctul de vedere al serverului web a fost complet bine.
Dar ați solicitat index.html.
Ați solicitat shuttle.js și service.js.
Și a fost capabil să se întoarcă succes pentru tine toate aceste lucruri -
200.
OK.
Este doar atunci când browser-ul a încercat să interpreta codul JavaScript care
E ca si cum, stai, acest lucru nu este eroare JavaScript valid.
Orice alte întrebări?
Bine.
>> David J. MALAN: Deci, data viitoare up a fost numărul 11.
Și 11 a fost mai infricosatoare pentru o mulțime de oameni.
Deci, cel mai important lucru de reținut aici a fost că aceasta a fost, într-adevăr, despre
o listă de două ori legat.
Dar acest lucru nu a fost la fel ca anul trecut probleme legate de două ori listă,
care nu i-ai dat avertismentul că lista ar putea, de fapt, să fie nesortat.
>> Deci, faptul că lista a fost nesortate și faptul că acest cuvânt a fost
a subliniat acolo a fost menit să transmită că aceasta este de fapt o simplificare
a ceea ce altfel ar fi fost o problemă mai dificilă
și unul mai lung.
Deci, o greșeală comună aici a fost de a fi pus soluție de anul trecut pe o dvs.
pager și apoi doar să copiați orbește că în jos ca răspuns, care este dreptul
răspunsul la o altă întrebare similară în spirit.
Dar subtilitățile aici au fost următoarele.
>> Deci unul, ne-am declarat și un nod definite în mod obișnuit aici.
Apoi ne-am definit lista de fi un global pointer inițializat la null.
Apoi, se pare, există două funcții avem prototipuri de aici, se introduce
și elimina.
Și apoi ne-am unele mostre de cod aici de a face o grămadă de inserții.
Și apoi am să vă întreb pentru a finaliza punerea în aplicare a insera mai jos, în astfel de
un mod care introduce n în lista în timp constant, de asemenea, a subliniat,
chiar dacă sunt deja prezente.
>> Deci, frumusetea de a fi capabil de a introduce în timp constant, este că aceasta implică
care va trebui să introduceți noul nod unde?
În partea din față.
Deci, se elimina, din fericire, cel puțin unul dintre cazurile care utilizate pentru a solicita
și mai multe linii de cod, cum ar fi făcut-o anul trecut și chiar în clasă, atunci când ne-am
a vorbit prin acest tip de lucru cu oamenii și cu unele
cod pseudo verbal.
Astfel încât în ​​soluția de aici, să săriți peste pentru că doar pentru a avea o privire la vizual
ecranului.
>> Observați că facem următoarele.
Și, de asemenea, observa alte simplificarea a fost că, chiar dacă este
deja prezent, astfel încât acest lucru înseamnă, chiar dacă numărul este deja acolo, puteți
doar introduceți orbește un alt copie a acesteia.
Și că, de asemenea, a fost menit să fie un simplificare, astfel încât ai putea
concentreze asupra, într-adevăr, unele dintre cele mai parte intelectual interesant și
nu doar unele erori suplimentare de verificare având în vedere timpul limitat.
>> Deci, în această soluție etalon, sa aloce un pointer pe de-o parte stânga
alta aici pentru un nod.
Acum, dau seama că pointer, ca Rob a spus, este de numai 32 de biți.
Și nu conține de fapt o adresă până când
atribuie adresa.
Și facem asta pe-dreapta lateral prin malloc.
Ca un bun cetățean, vom verifica ca malloc nu este, de fapt, nul, astfel încât
noi nu creează accidental o segfault aici.
Și de fiecare dată când utilizați malloc în viață, te ar trebui să fie de verificare pentru nul, ca nu cumva
aveți un bug subtil.
>> Apoi ne-am inițializa că nul de atribuirea n și anterior și următor.
Și în acest caz aici, am initializat anterior la nul, deoarece acest nou
nod va fi noul începând din lista mea.
Deci nu va fi nimic înainte de a fi.
Și vreau să adăugați, în esență, listă existentă la noul nod de
stabilirea lângă egal cu sine însuși lista.
Dar eu nu am terminat încă.
Deci, dacă lista de sine exista deja, și există cel puțin un nod
deja în vigoare, în cazul în care aceasta este lista aici și am introduce un nou nod aici, am
trebuie să vă asigurați că fostul meu nod punctele înapoi la noua mea nod,
deoarece aceasta este, din nou, o listă de două ori legat.
>> Așa că am face o verificare bun-simț.
Dacă lista nu este nul, în cazul în care există deja unul sau mai multe noduri de acolo, apoi
adăuga că înapoi referire ca să spunem așa.
Și apoi ultimul lucru de care avem nevoie să faceți este de fapt actualizarea global
Lista de variabile se la punctul la care nod nou.
Da.
>> Audiența: În săgeata pointer [Inaudibil] este egal cu zero, nu ca
a face cu lista, deoarece lista este nul?
>> David J. MALAN: Nope.
Că este pur și simplu mi-a fi proactiv atentă, în care, dacă acest lucru este meu
Lista originală cu poate unele mai multe noduri aici și eu sunt introducerea mea
nod nou pe aici, nu se întâmplă să fie nimic pe aici.
Și vreau să captura că ideea prin stabilirea anterioară a
null pe noul nod.
Și, probabil, în cazul în care codul meu este corect și nu există nici o altă cale de a insera
altele decât această funcție noduri, probabil, chiar dacă lista are deja
unul sau mai multe noduri în ea, probabil lista, primul nod, ar avea o
pointer anterioară de nul sine.
>> Audiența: Și doar un follow-up.
Motivul pentru care ai pus pointer următoarele egali Lista este faci indicatorul
înainte de listă în care se indică la alta, cred -
Eu nu -
doar liste?
>> David J. MALAN: Exact.
Și așa să considerăm de fapt două cazuri aici într-adevăr, chiar dacă
pentru a le vom lua în considerare nu este destul de similară codului.
Dar la un nivel ridicat, dacă aceasta reprezintă Lista iar acest lucru este un 32-bit
pointer, cel mai simplu scenariu este că acest lucru este nulă în mod implicit.
Și să presupunem că vreau să inserați numărul 50 a fost primul număr.
Așa că am de gând să merg mai departe și să aloce un nod, care se întâmplă să conțină
trei domenii -
n, anterior, și următorul.
>> Am de gând să pună la numărul 50 aici, deoarece acest lucru va fi n.
Acest lucru va fi următorul.
Și acest lucru va fi trecut.
Și ce să fac în acest caz?
Ei bine, am făcut doar o linie aici.
Pointer n devine n.
Eu atunci spun, anterior ar trebui sa null.
Deci, acest lucru va fi nul.
Apoi m-am de gând să spun următorul este de gând pentru a obține lista.
>> Și asta doar funcționează bine.
Acest lucru este nul.
Și așa spun, noul nod Next domeniu ar trebui să obțineți tot ce este.
Astfel că pune un alt nul acolo.
Și apoi ultimul lucru Eu nu se verifica aici.
Dacă lista nu este egal cu zero, dar este egal cu zero, asa ca am sări ca
totul.
Și așa tot ce fac în continuare lista devine pointer, ceea ce duce pictural în
o imagine de genul asta.
Deci asta e un scenariu.
>> Și cel care te-au întrebat despre în mod special este o situație ca aceasta,
unde avem deja o listă de-un nod.
Și dacă mă duc înapoi în original declarația problemă, viitoare vom
introduceți spun este de 34, doar pentru de dragul discuției.
Așa că am de gând să doar convenabil trage că pe aici.
Tocmai am malloced.
Să presupunem că eu sunt de verificare pentru nul.
>> Acum, am de gând pentru a inițializa n să fie 34.
Și acest lucru va fi n.
Acest lucru va fi următorul.
Și acest lucru va fi trecut.
Să ne asigurăm că nu am făcut- obține acest înapoi.
Anterior este pe primul loc în definiție.
Lasă-mă să rezolv asta.
Aceasta este anterioară.
Acest lucru este următorul.
Chiar dacă acestea sunt identice, Să-l păstrați consistent.
>> Anterior.
Acest lucru este următorul.
Deci, eu doar am malloced nota mea, verificat pentru nul, atribuit 34 în nodul.
Anterior devine nul.
Așa că mi-a dat asta.
Următor devine listă.
Deci, lista este aceasta.
Deci, aceasta este la fel acum ca desen aceasta săgeată, astfel încât ele indică o
în același.
Și apoi voi verifica dacă lista de nu este egal cu zero.
Și nu e de data asta.
Apoi, am de gând să fac lista anterior devine pointer.
>> Deci, lista precedentă devine PTR.
Deci, acest lucru are efectul de a pune o săgeată grafic aici.
Și că e cam ondulat, liniile.
Și apoi, în cele din urmă, am actualiza lista de la punctul de pointer.
Deci, acum aceasta puncte de la tipul ăsta.
Și acum, hai să facem o rapidă cec bun-simț.
>> Iată lista, care este variabila la nivel mondial.
Primul nod este, într-adevăr, 34, deoarece Am urmând ca săgeata.
Și asta e corect pentru că vreau să se introduce la începutul listei
toate nodurile noi.
Sa câmp de lângă mine duce la acest tip.
Dacă eu continui, m-am lovit următor este nul.
Deci, nu mai e listă.
Dacă am lovit anterior, am înapoi unde am aștepta.
>> Deci, există încă câteva indicii, în mod evident, pentru a manipula.
Dar faptul că s-au spus să faci aceasta în timp constant tine înseamnă doar
au un număr finit de lucruri ai voie să faci.
Și ceea ce este faptul că numărul?
Acesta ar putea fi un pas.
Ar putea fi două.
Ar putea fi de 1.000 de pași.
Dar este finit, ceea ce înseamnă că nu se poate au nici un fel de looping se întâmplă
aici, nu recursivitate, nici bucle.
Este doar trebuie să fie linii greu codificate- de cod așa cum avem în această probă.
>> Deci, următoarea problemă 12 ne-a cerut să finalizeze punerea în aplicare a elimina
mai jos în așa fel încât ea elimină n din lista în timp liniar.
Astfel încât să aibă un pic mai mult loc de manevră acum.
S-ar putea presupune că n, dacă este prezent in lista, va fi prezent
nu mai mult de o dată.
Și că prea este menit a fi o baza de test presupunere simplificarea, așa
că dacă veți găsi numărul 50 undeva în listă, nu face, de asemenea,
trebuie să vă faceți griji cu privire la continuarea repeta, în căutarea pentru orice posibile
copie de 50, ceea ce ar decurge doar în unele punct caracteristic în timp limitat.
>> Deci, cu remove, acesta a fost cu siguranta mai provocatoare și mai mult
cod pentru a scrie.
Dar, la prima vedere, sincer, s-ar putea arata ceva de copleșitoare și ca
nu exista nici o modalitate de ai putea avea veni cu privire la un test.
Dar dacă ne concentrăm pe etapele individuale, sperăm, se va brusc
vi se pare că fiecare dintre aceste persoane trepte are sens evident
în retrospectivă.
Deci, haideți să aruncăm o privire.
>> Deci, în primul rând, ne-am inițializa pointer să fie lista sine.
Pentru că am nevoie de timp liniar, care înseamnă Am de gând să aibă o anumită buclă.
Și un mod comun de a repeta de-a lungul noduri într-o structură de listă sau orice fel
structurii iterativ este de a lua un pointer la partea din față a datelor
Structura și apoi începe doar actualizarea ea și de mers pe jos drumul tau
prin structura de date.
Așa că am de gând să facă exact acest lucru.
>> În timp ce pointer, variabila mea temporară, nu este egal cu zero, să
mergeți mai departe și să verificați.
V-am noroc?
Este domeniul n în nodul Eu sunt în prezent uita la egal la
număr caut?
Și dacă da, hai sa facem ceva.
Acum, observa acest lucru în cazul în care condiție înconjoară întregul
Următoarele linii de cod.
Acesta este singurul lucru pe care mi pasă - găsirea unui număr în cauză.
Deci nu e nici altcineva, care simplifică conceptual lucrurile un pic.
>> Dar acum, am realizat, și s-ar putea avea numai realizat acest lucru după gândire
printr-un pic, nu e de fapt, două cazuri de aici.
Unul este în cazul în care nodul este la începutul listei, care este o
puțin enervant, pentru că este o caz special, pentru că trebuie să se ocupe
cu acest lucru, care este singura anomalie.
Peste tot în listă, e același lucru.
Există un nod anterior și un viitor nod, nodul anterior, nod următor.
Dar tipul ăsta este un pic mai special dacă e la început.
>> Deci, dacă indicatorul este egal cu lista în sine, așa că, dacă eu sunt la început de
lista și am găsit n, am nevoie de pentru a face o serie de lucruri.
Unul, am nevoie pentru a schimba lista de punctul de la câmpul următor, 50.
Deci, să presupunem că am încercat pentru a elimina 34.
Deci, acest tip trebuie să plec departe într-o clipă.
>> Așa că am de gând să spun, lista devine pointer următor.
Ei bine, acest lucru este pointer.
Următor indică aici.
Deci, acest lucru se schimba această săgeată dreapta acum pentru a indica tipul ăsta de aici.
Acum, amintiți-vă, avem o variabilă temporară.
Deci, nu am nici orfani noduri, pentru că am avea, de asemenea, acest tip în mea
punerea în aplicare a elimina.
Deci, acum, dacă lista în sine nu este nul, Am nevoie de a stabili ceva.
>> Am nevoie pentru a face acum siguri că această săgeată, care este îndreptat în prealabil
50-34, aceasta a ajuns să plece, pentru că dacă am încercat să scape
de 34, 50 a avut mai bine nu menține nici o un fel de trimitere înapoi la el ca la
săgeată sugerat.
Așa că am făcut doar această linie.
Deci, atunci am terminat.
Acest caz este de fapt destul de ușor.
Tocare capul listei este relativ simplă.
>> Din păcate, nu există acest bloc enervant altceva.
Deci, acum, trebuie să ia în considerare în cazul unde nu e ceva la mijloc.
Dar nu e prea teribil, cu excepția pentru sintaxa de genul asta.
Deci, dacă nu sunt la începutul lista, eu sunt undeva la mijloc.
Și aceasta linie de aici este de a spune, start la orice nod esti la.
Du-te la următorul câmp nodul precedent și subliniază că la indicatorul.
>> Să facem acest lucru pictural.
Care a fost obtinerea complicat.
Deci, dacă am avea un domenii anterioare de aici - hai sa facem acest lucru - următoarele domenii de aici.
Am de gând să simplifice indicii mei, mai degrabă trage decât o grămadă de
lucrurile înainte și înapoi intersectează reciproc.
Și acum, hai să spun acest lucru este de 1, 2, 3 de dragul discuției, chiar
însă că nu se aliniază cu problema în cauză.
>> Deci, aici e lista mea legată.
Am încercat pentru a elimina doi în acest versiune special a poveștii.
Așa că am actualizat pointer la să fie îndreptată la tipul ăsta.
Deci, aceasta este PTR.
A îndreptat aici.
Aceasta este lista, care există la nivel global, ca și mai înainte.
Și el a îndreptat aici, indiferent de ce.
Și acum, eu sunt încercarea de a elimina două.
>> Deci, dacă pointer este îndreptat aici, eu sunt va urma, se pare,
pointer anterior, care ma pune la 1.
Am apoi de gând să spun că în următorii domeniu, care ma aduce pe la acest
caseta aici, se va egal pointer următor.
Deci, dacă acest indicator, acesta este următorul.
Asta înseamnă că aceste săgeți nevoile la punctul de acest tip.
>> Deci, ce această linie de cod are doar făcut este un pic de acest lucru.
Iar acum, acest lucru este sa arate ca un pas în direcția cea bună.
În esență, vrem să croitor 2 din din mijlocul 1 și 3.
Deci, este logic că vrem să traseu acest indicator în jurul ei.
Deci, această linie viitor este verificarea dacă indicatorul următor nu este nul, există
într-adevăr cineva la dreapta de 2, Asta înseamnă că trebuie, de asemenea, de a face
un pic de croitor aici.
>> Deci, acum am nevoie să urmeze acest indicator și actualizează indicatorul anterior pe
acest tip de a face un pic de o workaround aici punctul de aici.
Și acum, acest punct de vedere vizual este frumos.
E un pic cam dezordonat în care nu există nimeni nu a mai îndreptat la 2.
2 indică spre stânga.
Și 2 indică spre dreapta.
Dar el poate face ce vrea, deoarece e pe cale să se elibereze.
Și nu contează ce aceste valori mai sunt.
>> Ceea ce este important este că restul de baieti sunt de rutare de mai sus
și sub el acum.
Și într-adevăr, asta e ceea ce facem în continuare.
Noi pointer gratuit, ceea ce înseamnă că spune sistem de operare, sunteți bineveniți
pentru a revendica acest lucru.
Și apoi în cele din urmă, ne-am întoarce.
Altfel implicit, dacă ne-am nu s-au întors încă,
Trebuie să continui să cauți.
Deci, indicator este egal cu pointer viitor doar înseamnă muta tipul ăsta de aici.
Muta tipul ăsta de aici.
Muta tipul ăsta de aici în cazul în care, în fapt, nu am găsit numărul de
căutăm încă.
>> Deci, sincer, se pare complet copleșitoare, cred că, la prima
vedere, mai ales dacă luptat cu aceasta în timpul testul apoi a se vedea
ceva de genul asta.
Și vă bate-te pe spate.
Ei bine, nu e nici un fel am putea avea veni cu care la testul.
Dar aș spune, poți, dacă te rupe se în jos, în aceste individuale
cazuri și doar plimbare prin ea cu grijă, deși, desigur, sub
circumstanțe stresante.
>> Din fericire, imaginea a făcut tot mai fericit.
Ai putea desena aceasta în orice număr de moduri.
Tu nu trebuie să faci intersectează lucru aici.
Ai putea-o face cu drept linii, cum ar fi acest lucru.
Dar esența acestei probleme, în general, a fost să realizeze că
imagine în cele din urmă ar trebui să arate un pic ceva de genul asta, pentru că
constanta de timp a sugerat că vă păstrați bruiaj și bruiaj și bruiaj
noi noduri la începutul listei.
Orice întrebări?
Probabil cele mai dificile de cu siguranță întrebări de codificare.
>> Audiența: Deci, lista similar capul în exemplele anterioare.
>> David J. MALAN: Exact, exact.
Doar un alt nume pentru o variabilă globală.
Lumea largă ce?
>> ROB BOWDEN: OK.
Deci, aceasta este cea în care a trebuit să scrie paragraf.
Unii oameni au scris eseuri pentru această întrebare.
Dar ai nevoie doar de a utiliza aceste șase termeni pentru a descrie ceea ce se întâmplă atunci când
încercați să contactați facebook.com.
Deci, voi vorbi doar prin procesul de folosind toate aceste termeni.
Deci, în browser-ul nostru, noi de tip facebook.com și apăsați Enter.
Deci, browser-ul nostru se va construi un HTTP cere ca aceasta va trimite
printr-un proces de Facebook pentru Facebook a răspunde la noi cu
HTML a paginii sale.
>> Deci, ceea ce este procesul de care cererea HTTP
ajunge de fapt la Facebook?
Deci, în primul rând, avem nevoie de a traduce Facebook.com.
Deci, doar dat numele Facebook.com, în cazul în care face, de fapt, cererea HTTP
nevoie pentru a merge?
Deci, avem nevoie de a traduce Facebook.com la o adresă IP, care unic
identifică ce masina am de fapt, doriți să trimiteți această cerere.
Laptop-ul are o adresă IP.
Nimic conectat la internet are o adresă IP.
>> Deci DNS, Domain Name System, care este ce se întâmplă să se ocupe de traducerea
de la facebook.com la o adresă IP care tu de fapt vrei sa contacteze.
Așa că am contacta serverele DNS și să zicem, ceea ce este facebook.com?
Se spune, oh, este adresa IP 190.212 ceva, ceva, ceva.
Bine.
Acum, eu știu ce mașină Vreau să contactați.
>> Deci, atunci va trimite cererea dvs. HTTP pe la acel aparat.
Deci, cum se ajunge la acest aparat?
Ei bine, cererea trece de la router la router viguros.
Amintiți-vă de exemplu în clasă, în cazul în care am văzut de fapt, traseul pe care
pachete luat când am încercat pentru a comunica.
Am văzut-l sari peste Atlantic Ocean la un moment dat sau orice.
>> Astfel încât portul ultimul termen.
Deci, acest lucru este acum pe computer.
Puteți avea mai multe lucruri în prezent comunicarea cu internetul.
Deci, eu pot fi difuzate, de exemplu, Skype.
S-ar putea avea un browser web deschisă.
S-ar putea avea ceva care torrenting fișiere.
Deci, toate aceste lucruri sunt Comunicarea cu
internet într-un fel.
>> Deci, atunci când computerul primește unele date de pe internet, cum se face
știu ce aplicație de fapt vrea datele?
Cum se știe dacă acest lucru special Datele se înțelege pentru
torrenting cerere, spre deosebire de pentru browser-ul web?
Deci, acesta este scopul de porturi în care toate aceste aplicații au
a susținut un port de pe computer.
Deci, browser-ul web, spune, hei, Ascult pe portul 1000.
Și programul torrenting spune, Ascult pe portul 3000.
Și Skype spune, eu sunt, folosind portul 4000.
>> Deci, atunci când obține unele date de care aparține la una din aceste aplicații, datele
este marcat cu ce port este de fapt ar trebui să fie trimise de-a lungul a.
Deci acest spune, oh, eu aparțin la portul 1000.
Știu că atunci am nevoie de a transmite prezenta de-a lungul a browser-ul meu de web.
Deci, motivul pentru care este relevant aici este că serverele web au tendința de a
asculta pe portul 80.
Așa că atunci când am contacta Facebook.com, eu sunt comunicarea cu unele mașini.
Dar trebuie să spun care portul de care mașină vreau să comunic cu.
Și servere de web tind să fie asculta pe portul 80.
>> Dacă ar fi vrut, ei ar putea stabili , astfel se enumeră ca pe portul 7000.
Și apoi într-un browser web, am putut manual de tip Facebook.com: 7000 la
trimite cererea la portul 7000 de server de web Facebook.
>> David J. MALAN: Și în acest caz, chiar deși nu am nevoie ca oamenii
menționeze acest lucru, în acest caz, ce port ar solicitarea merge de fapt, la?
Încercați din nou.
Exact.
Nu caută asta, dar o subtilitate că e acolo nimeni ultimul.
>> ROB BOWDEN: Deci, HTTPS, din moment ce este ascultare în mod special pentru
criptat, e pe portul 4430.
>> Audiența: și e-mailuri sunt 25, nu?
>> David J. MALAN: Outbound e-mailuri, 25, da.
>> ROB BOWDEN: Eu nici măcar nu știu de cele mai multe - toate din cele mai mici tind să fie
rezervat pentru lucruri.
Cred că totul sub 1024 este rezervat.
>> Audiența: De ce ai spus 3 a fost numărul greșit?
>> ROB BOWDEN: Pentru că într-o adresă IP, există patru grupuri de cifre.
Și ei sunt la 0 la 255.
Deci, 192.168.2.1 este o comună local, adresa de IP de rețea.
Observați toate acestea sunt mai puțin de 255.
Așa că atunci când am început cu 300, care nu ar fi putut, eventual,
a fost unul din numerele.
>> David J. MALAN: Dar clip prost de - a fost CSI, unde au avut o
număr care a fost prea mare pentru adresa IP.
>> ROB BOWDEN: Orice întrebări cu privire la acest lucru?
Următoarea, schimbarea atât de completă în subiect, dar avem această matrice PHP pentru
casele din curte.
Și avem o lista neordonata.
Și vrem să imprimați fiecare element din listă conține doar numele casei.
Deci, avem o buclă foreach.
Deci, amintiți-vă, sintaxa este foreach matrice ca element în matrice.
Deci, prin fiecare iterație a buclei, casa este de gând să ia pe unul dintre
valori în interiorul de matrice.
>> La prima iterație, casa va fi Cabot House.
Pe o repetare a doua, casa va fi fi Courier Casa și așa mai departe.
Deci, pentru fiecare quad ca casă, suntem doar de gând să imprima -
De asemenea, ar putea fi repetat -
elementul din listă și apoi numele casei și apoi închideți elementul din listă.
Acolade sunt opționale aici.
>> Și apoi ne-am spus, de asemenea, în problema în sine, amintiți-vă pentru a închide
tag-ul lista neordonata.
Deci, avem nevoie pentru a ieși din modul PHP în scopul de a face acest lucru.
Sau am putea fi repetat închide tag-ul lista neordonata.
>> David J. MALAN: De asemenea, ar fi bine aici au fost de a utiliza o școală veche de
buclă cu un $ i = 0 0 și utilizarea numărului de dau seama de lungimea razei.
Totul prea bine, doar un pic de wordier.
>> Audiența: Deci, dacă ai de gând să [Inaudibil], ai face -
Am uitat ce [inaudibil] este bucla.
Vrei $ suport quad i?
>> David J. MALAN: Exact.
Da, exact.
>> ROB BOWDEN: Altceva?
>> David J. MALAN: În regulă.
Compromisuri.
Deci, au existat legături de răspunsuri posibil ca fiecare dintre acestea.
Am fost într-adevăr în căutarea doar pentru ceva convingătoare pentru o cu susul și
un dezavantaj.
Și numărul 16 a întrebat, validarea utilizatorilor " input client-side, ca cu JavaScript,
în loc de server-side, ca și cu PHP.
Deci, ce este o cu susul de face client-side?
>> Ei bine, unul dintre lucrurile pe care le-am propus este pe care le reduce latenta, pentru că
nu trebuie să deranjez contactarea de server, care ar putea dura câteva
milisecunde sau chiar câteva secunde prin evitarea că și doar
validarea de intrare client-side utilizatorilor de declanșând un handler on-prezinte și
doar verificare, au tastați ceva in pentru nume?
S-au ceva de tip la adresa de e-mail?
S-au alege un cămin de la meniul drop-down?
>> Aveți posibilitatea să le dea un feedback instantaneu utilizând computerul GHz
sau orice ar avea asta de fapt, pe biroul lor.
Deci e doar o utilizare mai bună experiență de obicei.
Dar un dezavantaj de a face client-side validare, dacă o faci fără, de asemenea,
face validarea server-side este că cele mai multe oricine iese din CS50 știe
pe care le pot trimite doar datele pe care doriți la un server de orice număr de moduri.
Sincer, în cele mai multe orice browser, aveți posibilitatea să faceți clic în jurul în setările și doar
dezactiva JavaScript, care ar fi, prin urmare, dezactivați orice formă de
validare.
>> Dar tu, de asemenea, s-ar putea aminti că, chiar am a făcut unele lucruri secrete din clasa utilizând
telnet și de fapt pretinde a fi un browser prin trimiterea get
cereri de la un server.
Și care, cu siguranță nu este folosind orice JavaScript.
Asta e doar de mine tastarea comenzilor la o tastatură.
Deci, într-adevăr, orice programator in cadrul suficient confort cu web și HTTP
ar putea trimite orice date de el sau ea vrea la un server fără validare.
Și în cazul în care server-ul dvs. nu este, de asemenea, verificarea, mi-au dat un nume, este
acest fapt o adresă de email validă, a făcut ei aleg un cămin, s-ar putea sfârși
up introducerea fals sau pur și simplu de date gol în baza de date, care, probabil,
nu va fi un lucru bun dacă ai fost presupunând că a fost acolo.
>> Deci, aceasta este o realitate enervant.
Dar, în general, client-side Validarea este mare.
Dar aceasta înseamnă de două ori la fel de mult de lucru.
Deși nu există diverse biblioteci, biblioteci JavaScript pentru
exemplu, că fac acest lucru de mult, mult mai puțin de o durere de cap.
Și aveți posibilitatea să reutilizați o parte din codul server-side, client-side.
Dar își dau seama că aceasta este de obicei muncă suplimentară.
Da.
>> Audiența: Deci, dacă ne-am a spus mai puțin sigure -
>> David J. MALAN: [râde]
Uf.
Acestea sunt întotdeauna mai greu cele de a dispune.
>> ROB BOWDEN: Asta ar fi au fost acceptate.
>> David J. MALAN: Ce?
>> ROB BOWDEN: Am creat această problemă.
Care ar fi fost acceptate.
>> David J. MALAN: Da.
>> Audiența: cool.
>> ROB BOWDEN: Dar nu am acceptat pentru primul -
bine, ceea ce am fost căutați este ceva de genul nu trebuie să
să comunice cu serverul.
Noi nu a acceptat doar mai repede.
>> Audiența: Ce despre Nu reîncărcați pagina?
>> ROB BOWDEN: Da.
Asta a fost un răspuns acceptate.
>> David J. MALAN: Orice unde ne-am simțit a fost mult mai probabil decât improbabil
că ai știut ce ai fost zis, care este un dur
linie pentru a desena, uneori.
Folosind o listă legată loc de o matrice pentru a menține o
Lista de numere întregi sortate.
Astfel încât o cu susul în noi de multe ori cita cu legat liste care au motivat întreaga lor
introducere a te dinamism.
Ele se pot dezvolta.
Ei pot contracta.
Deci, nu trebuie sa sara prin cercuri pentru a crea de fapt, mai mult de memorie
cu o matrice.
Sau nu trebuie să doar spun, îmi pare rău, de utilizator.
Matricea este umplut.
Creștere atât de dinamică a listei.
Un dezavantaj deși a listelor legate?
>> Audiența: Este liniar.
Caută pe lista legat este liniar în loc de ceea ce autentifica
>> David J. MALAN: Exact.
Caută pe o listă de legate este liniar, chiar dacă este sortat, pentru că puteți
urmați doar aceste pesmet, acestea indicii, de la începutul listei
până la sfârșit.
Nu puteți utiliza cu acces aleator și, astfel, binar de căutare, chiar dacă e
sortate, pe care ai putea a face cu o matrice.
Și există, de asemenea, un alt cost.
Da.
>> Audiența: memorie ineficient?
>> David J. MALAN: Da.
Ei bine, eu nu ar fi neapărat spune ineficiente.
Dar ea nu costa mai mult de memorie, pentru că aveți nevoie de 32 de biți pentru fiecare
nod pentru indicatorul suplimentar, la cel puțin pentru o listă individual legat.
Acum, dacă sunteți stocarea doar numere întregi și când adăugați indicatorul, care este
de fapt, un fel de non-trivial.
Este dublarea cantității de memorie.
Dar, în realitate, dacă sunteți stocarea un Lista legate dintr-o structura care ar putea avea
8 bytes, 16 bytes, chiar mai mult decât că, poate e mai puțin
de un cost marginal.
Dar este un cost, totuși.
Deci, fie de cei care s-ar fi fost bine ca dezavantaje.
>> 18.
Folosind PHP în loc de C pentru a scrie un program de linie de comandă.
Deci, aici, este de multe ori mai rapid de a utiliza un limbă ca PHP sau Ruby sau Python.
Trebuie doar deschide rapid un editor de text.
Ai mult mai multe funcții disponibile pentru tine.
PHP are chiuveta de bucatarie de funcții, în timp ce în C, vă
au foarte, foarte puțin.
De fapt, voi știu la fel de greu că nu aveți tabele de dispersie.
Tu nu au legat liste.
Dacă le doriți, trebuie să le pună în aplicare tu.
>> Deci, una peste cap de PHP sau într-adevăr orice limbaj interpretat este rapiditatea
cu care puteți scrie cod.
Dar un dezavantaj, am văzut acest lucru atunci când am biciuit rapid un misspeller
punerea în aplicare în curs, folosind PHP, este că, folosind un limbaj interpretat
este de obicei mai lent.
Și am văzut că demonstrabil cu o crește în timp de 0.3 secunde la 3
secunde, datorită interpretării care se întâmplă de fapt.
>> Un alt susul a fost că Nu trebuie să compilați.
Deci, de asemenea, accelerează dezvoltarea De altfel, pentru că nu aveți
doi pași pentru a rula un program.
Trebuie doar una.
Și așa că e destul de convingătoare, de asemenea.
Folosind o bază de date SQL în loc de un fișier CSV pentru a stoca date.
Bazei de date astfel SQL este folosit pentru pset7.
Fișiere CSV nu ați folosit prea mult.
Dar ai folosit indirect în pset7 ca bine vorbind la Yahoo Finance.
>> Dar CSV este la fel ca un fișier Excel, dar super-simplu, în cazul în care coloanele sunt
doar demarcate de virgule în interiorul a unui fișier text altfel.
Și cu ajutorul unei baze de date SQL este un pic mai convingătoare.
Este o cu susul în, pentru că veți obține lucruri ca selecta și a insera și a șterge.
Și veți obține, probabil, indici care MySQL și a altor baze de date, cum ar fi
Oracle, construim pentru tine în memorie, care înseamnă selectați dvs. nu este, probabil,
O să fie de sus în jos liniar.
Este de fapt o să fie ceva cum ar fi căutare binar sau ceva
similară în spirit.
Astfel încât acestea sunt, în general, mai repede.
>> Dar un dezavantaj este că e doar mai mult de lucru.
Este mai mult efort.
Trebuie să înțeleagă bazele de date.
Trebuie să-l înființeze.
Aveți nevoie de un server pentru a rula că baza de date pe.
Aveți nevoie pentru a înțelege cum să-l configurați.
Deci, acestea sunt doar acestea tipuri de compromisuri.
În timp ce un fișier CSV, puteți creați-l cu gedit.
Si tu esti bine să plec.
Nu e nici o complexitate dincolo de asta.
>> Folosind un trie în locul unui tabel hash cu înlănțuire separat pentru a stoca o
dicționar de cuvinte care amintesc de pset5.
Deci, un incearca susul, în teorie cel puțin, este ceea ce?
Constantă de timp, cel puțin dacă ești hash pe fiecare individului
litere într-un cuvânt, ca tine ar putea avea pentru pset5.
Care ar putea fi de cinci hash-uri, șase hash în cazul în care există cinci sau șase
litere din cuvânt.
Și asta e destul de bine.
Și dacă există o limită superioară cu privire la modul lung cuvintele tale ar putea fi, asta e
timp într-adevăr asimptotic constant.
>> În timp ce un tabel hash cu separat înlănțuire, problema acolo cu
tip de structură de date este că performanța de algoritmi de obicei,
depinde de numărul de lucruri deja în structura de date.
Și asta e cu siguranță cazul cu lanțuri, prin care mai multe lucruri pe care le pune
într-un tabel hash, cu cât cei lanțuri du-te, ceea ce înseamnă, în cel mai rău
caz, ceea ce ar putea fi cautati pentru este tot drumul la capătul uneia
dintre aceste lanțuri, care efectiv revine în ceva liniar.
>> Acum, în practică, aceasta ar putea absolut fi cazul în care un tabel hash cu
lanțuri este mai rapid decât un corespunzătoare punerea în aplicare a trie.
Dar asta e pentru diverse motive, printre care se încearcă folosi o mulțime de
memorie care poate, de fapt, lucrurile lent în jos, pentru că nu te frumos
beneficii de ceva numit caching, în cazul în care lucrurile care sunt aproape împreună
în memorie pot fi accesate de multe ori mai rapid.
Și, uneori, pot veni cu o funcție foarte bun hash.
Chiar dacă trebuie să pierdeți un pic de memorie, s-ar putea, într-adevăr, să fie în măsură să
găsi lucruri rapid și nu la fel de rău ca și liniar.
>> Deci, pe scurt, nu a fost neapărat cu oricare dintre acestea una sau chiar două
anumite lucruri am fost în căutarea pentru.
Într-adevăr ceva convingător ca o cu susul și dezavantaj
în general, prins ochiul nostru.
>> ROB BOWDEN: Deci, pentru sensul creșterii, am făcut nu acceptă ca atare "mai repede." Tu
a avut de spus ceva despre asta.
Chiar dacă mi-ai spus teoretic mai repede, am știut că ai un fel de înțeles
că este 0 din 1.
Și tabel hash, în teorie, nu este 0 din 1.
Menționat nimic despre execuție în general, ai puncte.
Dar "mai repede", cele mai multe dintre soluțiile pe placa de mare care s-au neau
obiectiv mai lent decât soluțiile care au fost tabele de dispersie.
Atât de repede în sine nu este adevărat.
>> David J. MALAN: Dom de dom dom.
Probabil sunt singurul care își dă seama asta e modul în care ar trebui să
fi pronunțată, corect?
>> ROB BOWDEN: Am avut de fapt nici o idee.
>> David J. MALAN: Ea a făcut sens în capul meu.
>> ROB BOWDEN: Fac asta.
OK.
Deci, aceasta este cea în care ați avut de a desena diagrama similar s-ar putea
s-au văzut pe examene trecute.
Așa că haideți să ne uităm la asta.
Deci, de la nodul HTML, avem două copii, cap și corp.
Așa că am ramifica - cap și corp.
Capul are o etichetă de titlu.
Deci avem un titlu.
>> Acum, singurul lucru pe care o mulțime de oameni a uitat este faptul că aceste noduri text sunt
elemente din acest copac.
Deci, aici se întâmplă să-i atragă la fel de ovale pentru a le diferenția de acestea
tipuri de noduri.
Dar observați, de asemenea, aici avem de sus, de mijloc, și de jos se va sfârși prin a fi
noduri text.
Deci, ai uita pe cei a fost oarecum de o greșeală comună.
>> Organismul are trei copii - aceste trei divs.
Deci div, div, div și apoi textul copii nod ale acestor divs.
Asta e destul de mult pentru că întrebările.
>> David J. MALAN: Și este demn de remarcat, chiar dacă noi nu insista pe aceste
detalii în timp vom cheltui pe JavaScript, că ordinea nu, în
De fapt, materia de vedere tehnic.
Deci, dacă cap vine în fața corpului în HTML, atunci ar trebui să apară la
stângă a corpului în DOM real.
Care sa este, în general, doar FYI, ceva numit pentru documente, în cazul în care
contează.
Și dacă ați fost de punere în aplicare un parser, un program care citește HTML în clădire
up copac în memorie, pentru a fi sincer, asta e intuitiv, probabil, ceea ce
face oricum - de sus în jos, la stânga la dreapta.
>> ROB BOWDEN: Întrebări pe care?
Ar trebui să fac următoarea?
>> David J. MALAN: Sigur.
>> ROB BOWDEN: OK.
Deci, aceasta este depășire de zonă tampon întrebare atac.
Principalul lucru este să recunoască aici este, bine, cum ar putea un truc adversar
acest program în executare cod arbitrar?
Deci argv1, prima linie de comandă argument pentru acest program, care poate fi
arbitrar de mult.
Dar aici suntem folosind memcpy pentru a copia argv1, care aici este bar.
Îl trece ca argument.
Și așa se ia de pe bara de nume.
>> Deci, suntem memcpying bar în acest tampon c.
Cât de multe bytes suntem copierea?
Ei bine, cu toate acestea mulți bytes bar se întâmplă la folosi, lungimea de acest argument.
Dar c este de numai 12 bytes larg.
Deci, dacă am introduce un argument linie de comandă care este mai mult de 12 bytes, suntem
de gând să se reverse acest special tampon.
Acum, cum ar putea un adversar truc programa în executarea de cod arbitrar?
>> Deci, amintiți-vă că aici principal este de asteptare foo.
Și așa, atunci apelurile principale foo.
Să trage acest lucru.
Deci avem stack nostru.
Și principal are un cadru stivă în partea de jos.
La un moment dat, apeluri principale foo.
Ei bine, imediat, apelurile principale foo.
Și așa foo devine propriul său cadru de stivă.
>> Acum, la un moment dat, foo este de gând să se întoarcă.
Și a mers întoarce Foo, trebuie să știm la ce linie de cod în interiorul de noi principal
au fost, în scopul de a ști unde ar trebui să reia, în principal.
Putem numi foo de la un întreg grămadă de locuri diferite.
Cum știm unde să se întoarcă?
Ei bine, avem nevoie pentru a stoca că undeva.
>> Deci, undeva chiar pe aici, ne-am stoca în cazul în care ar trebui să ne întoarcem la o dată
revine foo.
Și aceasta este adresa de revenire.
Deci, cum ar putea să ia un adversar avantaj în acest sens este faptul că
acest tampon C sunt stocate, să spune, chiar aici este c.
Deci avem 12 bytes pentru c.
Acest lucru este c.
Și acest lucru este inel stivă foo lui.
Deci, dacă utilizatorul introduce mai mult rău intenționat bytes de 12 sau se introduce o comandă
argument linie care este mai mult de 12 caractere, atunci vom
reverse acest tampon.
>> Putem continua.
Și la un moment dat, vom merge departe suficient ca să începem
suprascrie această adresă de retur.
Deci, odată ce ne-am suprascrie adresa expeditorului, acest lucru înseamnă că, atunci când foo
se întoarce, vom reveni la oriunde utilizator rău intenționat este o spune de către
indiferent de valoarea a intrat, prin orice caractere utilizatorul a introdus.
Și astfel, dacă utilizatorul rău intenționat este în curs de deosebit de inteligent, el poate avea această
a reveni la undeva în printDef Funcția sau undeva în malloc
funcție, oriunde arbitrar.
>> Dar chiar mai inteligent este ceea ce în cazul în care are utilizatorul reveni la dreapta aici.
Și apoi de a începe executarea ca aceste linii de cod.
Deci, la acel moment, utilizatorul poate introduce ce vrea în această regiune.
Și el are control complet peste program.
Întrebări cu privire la asta?
Deci, următoarea întrebare este complet reimplementare de foo în așa fel
că nu mai e vulnerabil.
>> Deci, există o serie de moduri ai fi putut face acest lucru.
Încă mai avem c numai fiind de lungime 12.
Ai fi putut fi schimbat acest lucru ca parte a soluției.
Am adăugat, de asemenea, o verificare pentru a face sigur de bare nu a fost nul.
Deși nu ai nevoie că pentru credit deplin.
Deci vom verifica mai întâi lungime șir de bar.
Dacă este mai mare decât 12, atunci nu fac de fapt copia.
Deci asta e un mod de fixare.
>> Un alt mod de fixare este în loc de având c fi doar de o lungime de 12, ea trebuie
fie de lungime strlen (bar).
Un alt mod de fixare este a de fapt doar se întoarcă.
Deci, dacă au ajuns doar scape de toate de acest lucru, dacă ai fi tocmai a șters toate
de linii de cod, ce-ar fi ajuns credit complet, deoarece această funcție
nu realiza de fapt nimic.
Este copierea linia de comandă argument în unele matrice în
cadru de stivă locale.
Și apoi lucru se întoarce.
Și orice ar fi realizat este plecat.
Deci, întoarcerea a fost, de asemenea, o suficientă mod de a obține credit deplin.
>> David J. MALAN: Nu este destul de spiritul de întrebarea dar acceptabil conform
spec. cu toate acestea.
>> ROB BOWDEN: Întrebări cu privire la orice de care?
Singurul lucru pe care cel puțin necesare pentru a fi compilarea cod.
Deci, chiar dacă tehnic, nu sunt vulnerabilă în cazul în care codul nu
compila, nu am acceptat asta.
Nu mai am întrebări?
OK.
>> David J. MALAN: Vrei pentru a spune acest titlu?
>> ROB BOWDEN: Nu.
>> David J. MALAN: Deci, în acesta, această a fost fie o veste bună sau vești proaste.
Aceasta este literalmente aceeași problemă ca primul test.
Și e aproape la fel problema ca pset1.
Dar a fost în mod deliberat simplificat pentru a fi o piramidă simplă, una care poate fi
rezolvate cu un ușor repetare simplu.
Și într-adevăr, ceea ce am fost obtinerea de la aici nu a fost atât de mult logica,
pentru că, probabil, de acest punct, esti mai confortabil decât ai fost
într-o saptamana cu de bucle sau de ce bucle, dar într-adevăr să tachineze pe langa care
esti un pic mai confortabil cu noțiune care PHP nu este vorba doar despre ceea ce
programare.
Acesta poate fi folosit ca o limbă pentru a scrie programe de linie de comandă.
>> Și într-adevăr, asta e ceea ce am încercat pentru a atrage atenția asupra.
Acesta este un program PHP linie de comandă.
Deci, cod C aici, în timp ce corecta în C, nu este corect pentru PHP.
Dar codul este într-adevăr la fel.
Dacă veți compara soluțiile pentru Quiz 0 împotriva Quiz 1, veți găsi că
este aproape identic, cu excepția unele semne de dolari și pentru
absența unui tip de date.
În special, dacă ne uităm aici, veți vedea că vom repeta, în acest
caz, de la 1 până la 7.
>> Am fi putut face o 0 index.
Dar, uneori, cred că e doar mental ușor să te gândești la lucruri
la 1 la 7.
Dacă doriți un bloc, apoi două blocuri, apoi trei, apoi
dot, dot, dot șapte.
Am j fiind inițializat la 1 și apoi de numărare pe de până la i.
Și totul aici este altfel identice.
Dar demn de reținut sunt un cuplu de lucruri.
Noi vă oferim aceste două linii, acest prim unul, goofily numit ca un shebang
pentru bang ascuțit.
Și care specifică doar calea, dosar, în care un program poate fi
a constatat că doriți să utilizați pentru a interpreta acest fișier.
>> Și apoi linia după care, de Desigur, înseamnă a intra în modul PHP.
Și linia de la partea de jos înseamnă modul de ieșire PHP.
Și funcționează, în general, cu interpretate de limbi.
Este un fel de enervant, dacă scrii un programul într-un fișier numit foo.php.
Și apoi utilizatorii trebuie să doar amintiți-vă, OK, pentru a rula acest program, am
trebuie să tastați "spațiu php foo.php." Fel de enervant, dacă nimic altceva.
Și, de asemenea, arată că programul dvs. este scris în PHP, care nu este tot
că iluminarea pentru utilizator.
>> Astfel încât să puteți elimina php. Totul amintesc de la curs.
Și vă puteți face de fapt. / Foo dacă l-ai schimbat atributele de ceea ce face
executabil.
Deci, chmod o + x foo-ar fi făcut asta.
Și dacă adăugați, de asemenea, shebang aici.
Dar, de fapt, problema a fost obtinerea de la imprimarea ceva de genul asta.
Nu HTML, nu C-cod cu siguranță, doar câteva PHP.
Deci, Milo apoi a revenit la problema 25.
Și în 25, s-au dat următoarele cod schelet, care a fost o
pagina web destul de simplu.
Și partea suculent HTML-înțelept a fost în jos aici, unde avem în interiorul corpului
un formular care are ID-ul unic de intrări în interiorul a ceea ce a fost de două intrări, una
cu o idee de nume, un cu o idee de buton.
>> Primul a fost de tip text, al doilea de tip prezinte.
Și așa v-am dat, de fapt, mai mult ingrediente decât ai nevoie, doar așa
voi avea opțiuni cu care pentru a rezolva această problemă.
Nu aveți nevoie de strict toate aceste ID-uri.
Dar vă permite pentru a rezolva în moduri diferite.
Și în partea de sus, observăm că obiectivul a fost de a declanșa
o fereastră ca aceasta -
Salut, Milo! -
a pop-up în browser-ul, folosind super-simplu, în cazul în care
nu urât, funcția de alertă.
Și astfel, în cele din urmă, aceasta se reduce conceptual de ascultare într-un fel de
trimise de client-side formă , Nu-partea de server, într-un fel
răspunde la faptul că prezentarea de către hapsân valoarea pe care utilizatorul tastat
în câmpul nume, și apoi afișarea în corpul unei alerte.
>> Deci, într-un fel, puteți face acest lucru este cu jQuery, care arată un pic
sintactic uimitoare la prima.
Puteți face acest lucru cu cod DOM pur - document.getelement de ID-ul.
Dar haideți să aruncăm o privire la această versiune.
Eu am o pereche de importante primelor linii.
Deci, avem această linie, care este identic cu ceea ce s-ar putea fi văzut
în, cred, form2.html de la clasă, în săptămâna 9.
Și acest lucru este să spun, executa următorul cod, atunci când
documentul este gata.
Acest lucru fiind importantă doar pentru că Pagini HTML sunt citite de sus a
jos, la stânga la dreapta.
>> Și, prin urmare, dacă încerci să faci ceva în cod aici la unele DOM
Element, unele tag-ul HTML, care este jos aici, o faci prea repede,
deoarece acest lucru nu are nici măcar a fost citit în memorie.
Deci, prin a spune acest lucru document.ready linie, ne spunem,
aici e un cod, browser-ul.
Dar nu executa acest lucru până când întregul document este gata, care este DOM
arbore există în memorie.
Acesta este un pic mai mult simplu, în cazul în care un punct de vedere sintactic
pic diferit, în cazul în care spun, apuca elementul HTML al cărui unic
identificator este intrari.
Asta e ceea ce tag-ul hash denotă, ID-ul unic.
Și apoi am sunat. Prezenta.
>> Deci. Prezenta aici este o funcție, în caz contrar cunoscut ca o metodă, care este
în interiorul obiectului de pe-o parte stânga side acolo că nu am evidenția.
Deci, dacă te gândești de intrări ca un obiect în memorie - și într-adevăr este.
Este un nod într-un copac -
. Să prezinte mijloace, atunci când acest formular cu acest ID este prezentat, executa
următorul cod.
Nu-mi pasă ce numele a Funcția este Sunt de executare.
Deci, aici eu sunt, folosind, ca și mai înainte, ceea ce este numit funcția lambda sau a unei
Funcția anonim.
Nu e deloc intelectual interesant decât acesta nu are nici un nume,
care este bine daca esti doar vreodată de gând să-l numesc o dată.
Si in interiorul acolo am descurca de fapt, depunerea formularului.
Declar în primul rând o variabilă numit valoare.
Și atunci care este efectul acestei a subliniat porțiune aici acum?
Ce face asta la o la nivel înalt pentru mine?
>> Audiența: Ea devine valoarea pe care utilizator nu a făcut în HTML de mai jos.
Ea devine ca ID-ul și apoi găsește valoarea de ea.
>> David J. MALAN: Exact.
Se apucă nodul, al cărui unic identificator este numele.
Ea devine valoarea de acesta, care este, probabil, ceea ce utilizatorul
el sau ea tastat.
Și apoi se stochează ca în variabila valoare numit.
Ca o paranteza, ai putea avea, de asemenea, făcut acest lucru un pic diferit.
Total acceptabil de a face ceva Valoarea minciună var devine
document.getElementById.
Și acest lucru este de ce este un pic obositor să nu folosească jQuery.
"Nume" valoare..
Deci, total acceptabil.
Moduri diferite de a face acest lucru. jQuery doar tinde să fie un pic mai succint și
cu siguranta mai populare printre programatori.
>> Acum, eu fac un pic de un bun-simț verifica, pentru că în problema
Declarația am spus în mod explicit, în cazul în care utilizator nu a fost încă introdus său
nume, nu arată o alerte.
Dar puteți verifica pentru că, doar prin verificarea șir gol pentru o
citat-citatul dacă există nimic de fapt acolo.
Dar dacă nu este egal cu citat-unquote, Vreau pentru a apela alerte.
Și partea interesantă aici este faptul că suntem folosind operatorul plus, care
ce face în JavaScript?
Înlănțui.
Deci, e ca operator de punct Phps.
Aceeași idee, sintaxă ușor diferită.
Și eu doar crearea șir care ai văzut pe captura de ecran -
Bună ziua, așa și așa.
>> Și apoi la ultimul detaliu este aceasta.
De ce nu mă întorc în interiorul false din această funcție anonim?
>> Audiența: Nu e nici o valoare.
Ai pus-o în formă.
Doar spune, în cazul în care valoarea nu este egal cu gol, atunci o fac.
Nu a fost un gol in care supunere.
>> David J. MALAN: OK.
Atenți, totuși.
Nu mai e nimeni aici.
Și că fals întoarcere este în afara de cazul în care condițiile.
Deci, această linie a subliniat, întoarce false, execută indiferent de ce, atunci când
formularul se depune.
Ce se întoarce în interiorul false din acest tratare a evenimentelor, așa cum se numește,
evenimentul în cauză fiind de depunere?
>> Audiența: Pentru că doar se întâmplă o dată.
>> David J. MALAN: Doar se întâmplă o dată.
Nu chiar.
Da?
>> Audiența: Acesta previne forma de depunerea la comportamentul implicit,
care ar face de start, reload.
>> David J. MALAN: Exact.
Deci, eu sunt supraîncărcarea termenul prezenta aici, pentru că eu spun, formularul este
fiind depuse.
Dar, așa cum sugerează, de fapt nu este fost prezentată în adevărata cale HTTP.
Când faceți clic pe Trimiteți, din cauza noastră handler onsubmit, suntem interceptarea
că depunerea formă ca să spunem așa.
Apoi vom face treaba noastră cu cod JavaScript.
Dar eu sunt în mod deliberat întorc false, pentru că ceea ce nu vreau să se întâmple o
fracțiune de secundă mai târziu, este pentru întreaga formă în sine pentru a fi prezentate la web
server cu perechi de valori-cheie, prin schimbarea URL-ul pentru a fi ceva de genul
q = pisici sau orice am făcut, de exemplu, in clasa.
Nu vreau să se întâmple, pentru că nu există nici o ascultare de server pentru această
forma de depunere.
Este pur în cod JavaScript.
Și de aceea nu am mai avea o acțiune atribut pe forma mea, pentru că am
nu intenționează ca acest lucru să du-te mereu la server.
>> Deci, este fiind depuse.
Dar suntem intercepta acea formă prezentarea și prevenirea implicit
comportament, care este de fapt să du-te tot drumul la server.
>> Audiența: Deci, menținându-l client-side.
>> David J. MALAN: Păstrarea aceasta client-side.
Exact dreapta.
Up următor a fost meu oh MySQL.
>> ROB BOWDEN: OK.
Deci, prima întrebare a fost, în general, dur pentru oameni.
Deși cele mai târziu a mers mai bine.
Așa că a trebuit să aleagă datele corect Tipuri de ambele coloane.
Și ambele au unele lucruri despre ei că
face o alegere dificilă.
Deci, int nu a fost o valid tip de număr.
Motivul fiind un cont de 12 cifre număr, un int nu este suficient de mare pentru a
stoca totalul cifre.
Deci, o alegere valabilă ar fi fost o mare int dacă se întâmplă să știi asta.
O altă opțiune ar fi putut fi un câmp char de lungime 12.
Deci, fie de cei care ar fi lucrat.
Int nu ar fi.
>> Acum, echilibru, cred că înapoi la pset7.
Așa că am folosit în mod specific pentru a zecimal stoca valoarea acțiunilor sau -
>> David J. MALAN: Cash.
>> ROB BOWDEN: Cash.
Am folosit zecimal pentru a stoca valoarea de numerar că utilizatorul are în prezent.
Deci, motivul pentru care face acest lucru este pentru că, amintiți-vă, pluteste.
Nu e în virgulă mobilă în precizie.
Nu se poate stoca cu precizie de numerar valori ca vrem aici.
Deci zecimal este capabil să exact magazin ceva, să zicem, două zecimale.
De aceea, echilibru, am dori să fie zecimal și nu plutesc.
>> David J. MALAN: Și, de asemenea, de asemenea, cu toate că ar fi fost inteligent în alte
contexte de a gândi, poate asta este o șansă pentru un int.
Voi păstra doar evidența lucruri în mărunțiș.
Pentru că am arătat în mod explicit implicit Valoarea de a fi 100.00, care
înseamnă că ar putea fi doar un int.
Și un alt subtilitate prea cu număr a fost că nu a fost menit
a fi o întrebare capcană.
Dar amintesc că un int în MySQL, în C, cel puțin în ca
aparat, este de 32 de biți.
Și chiar dacă nu vă așteptați să știu exact cât de multe cifre care
mijloace, mi aduc aminte că cel mai mare număr puteți reprezenta potențial
cu un număr de 32 de biți este de aproximativ ce?
>> Ce număr spunem mereu?
2 la 32, care este ceea ce aproximativ?
Nu trebuie să știe cu precizie.
Dar aproximativ este de ajutor în viață.
Este aproximativ 4 miliarde de euro.
Deci, ne-am spus că de câteva ori.
Știu că am spus că de câteva ori.
Și este de aproximativ 4 miliarde.
Și că este o regulă bună de degetul mare să știu.
Dacă aveți 8 biți, 256 este numărul magic.
Dacă aveți 32 de biți, 4 miliarde de da sau de a lua.
Deci, dacă doar vă notați 4 miliarde, veți vedea că este mai puține cifre decât
12, ceea ce înseamnă că nu este clar suficient de expresivitate a captura o
12 cifre numărul de cont.
>> ROB BOWDEN: OK.
Deci celelalte mers mai bine.
Deci, să presupunem că banca impune un lunar 20 dolari
Taxa de întreținere pe toate conturile.
Cu ce ​​interogare SQL ar putea banca deduce 20 dolari la fiecare număr, chiar dacă
aceasta duce la anumite solduri negative?
Deci, practic, există patru Principalele tipuri de interogări -
introduce, selecta, actualiza și șterge.
Deci, ce facem că suntem va folosi aici?
Actualizați.
>> Deci, haideți să aruncăm o privire.
Deci, aici suntem actualizarea.
Ce masă suntem actualizarea conturi?
Astfel actualizarea conturilor.
Și apoi sintaxa spune, ceea ce în conturile suntem actualizarea?
Ei bine, suntem setarea balansului egală cu Valoarea curent al balanței minus 20.
Deci, aceasta va actualiza toate rândurile de conturi, scăzând
20 dolari din soldul.
>> David J. MALAN: O greșeală comună aici, chiar dacă uneori iertat,
a fost de a avea de fapt cod PHP aici apelarea funcției de interogare sau punerea
ghilimele tot ceea ce nu trebuie să fie acolo.
>> ROB BOWDEN: Amintiți-vă că MySQL este un limbaj separat de PHP.
Se întâmplă să fi scris MySQL în PHP.
Și PHP este apoi trimite pe la serverul MySQL.
Dar nu aveți nevoie de PHP pentru a să comunice cu un server de MySQL.
>> David J. MALAN: Exact.
Deci, nu variabile, cu semne dolar ar trebui să fie în acest context.
Se poate face chiar tot de matematica în baza de date în sine.
>> ROB BOWDEN: OK.
Deci, următoarea.
Este aceasta cea viitoare?
Da.
Deci, cu ce interogare SQL ar putea banca prelua numerele de cont ale sale
mai bogate clienți, cei cu solduri mai mari de 1000?
Deci, care dintre cele patru tipuri principale vom vrea aici?
Selectați.
Așa că ne-o dorim pentru a selecta.
Ce ne dorim pentru a selecta?
Ce coloana vrem pentru a selecta?
Vom dori în mod special pentru a selecta numărul.
Dar dacă ai spus stele, ne-am de asemenea, acceptat faptul că.
>> Deci, selectați numărul din ce masa?
Conturi.
Și apoi condiția ne-o dorim?
În cazul în care soldul mai mare de 1.000.
De asemenea, am acceptat o mai mare mare sau egal.
Ultima.
Cu ce ​​interogare SQL ar putea banca aproape, adică, șterge fiecare cont de faptul că
are un echilibru de 0 dolari?
Deci, care dintre cele patru suntem de gând să doriți să utilizați?
Ștergeți.
Deci, sintaxa pentru asta?
Sterge de la ce masă?
Conturi.
Apoi condiție pe care ne-o dorim pentru a șterge -
în cazul în care soldul este egal cu zero.
Deci șterge toate rândurile din conturile unde echilibrul este zero.
Întrebări cu privire la oricare dintre acestea?
Vrei să stau la coadă?
>> David J. MALAN: Ghid de coadă.
Deci, în aceasta, v-am dat o oarecum structura familiar care am explorat-o
bit în clasă alături de structs, care a fost un date
Structura legate în spirit.
Diferența deși cu o coadă este care a trebuit să-și amintească într-un fel care
a fost la începutul cozii de așteptare, în mare parte, astfel încât să putem face mai mult
utilizarea eficientă a memoriei, cel puțin dacă am folosit o matrice.
>> Deoarece recall, dacă avem o matrice, în cazul în care, de exemplu, aceasta este partea din față a
coada, dacă am lua în coada de așteptare aici, și apoi cineva devine în linie
în spatele meu, în spatele meu, în spatele meu, și o persoană iese din linie, voi
ar putea, așa cum am văzut unele dintre noastre umane voluntari în clasă, au toată lumea
trecerea de acest fel.
Dar, în general, după ce toată lumea face ceva nu este cea mai bună utilizare a timpului
într-un program, pentru că înseamnă dvs. Algoritmul se execută în ceea ce
timp de funcționare asimptotic?
Este liniar.
>> Și mă simt ca și cum asta e un fel de stupid.
În cazul în care următoarea persoană în linie este următoarea persoană care ar trebui să meargă în
magazin, ei nu au toate să se mute împreună.
Doar lasa ca persoana să fie smuls atunci când vine momentul, de exemplu.
Astfel încât să putem salva un pic de timp acolo.
Și astfel de a face acest lucru, deși, ca mijloace că șeful de coada sau
fata de coada este de gând să muta progresiv mai adânc și mai adânc
în matrice și în cele din urmă s-ar putea de fapt, înfășurați în jurul valorii dacă utilizați un
matrice pentru a stoca oamenii în această coadă.
Astfel încât vă puteți gândi aproape a matrice ca o circulară de date
structura în acest sens.
>> Deci, va trebui cumva să țină evidența Dimensiunea de ea sau într-adevăr la sfârșitul anului acesta
și apoi în cazul în care la începutul anului este.
Deci, noi propunem ca voi declara o astfel de coadă, de asteptare
l q, doar o scrisoare.
Apoi, ne propunem ca să fie în față inițializat la zero și că dimensiunea
fi inițializat la zero.
>> Deci, chiar acum, nu e nimic în interiorul acestei coadă.
Și vă rugăm să completați punerea în aplicare a Puneți în coadă de mai jos în
astfel încât funcția adaugă n pentru sfârșitul q și apoi revine adevărat.
Dar în cazul în care q este plin sau negativ, Funcția ar trebui să se întoarcă în schimb false.
Și v-am dat un cuplu de ipoteze.
Dar ei nu sunt cu adevărat funcțional relevant, există doar că bool,
pentru că, tehnic, bool nu există în C decât dacă includ un
anumit fișier antet.
Astfel că a fost doar asigurați-vă că au fost nu este aceasta un truc
întrebare de genul ăsta.
>> Deci Puneți în coadă, am propus în eșantion soluții pentru a pune în aplicare după cum urmează.
Unul, vom verifica în primul rând usurinta, fructele low-agățat.
În cazul în care coada este plin sau numărul pe care încercați să introduceți este mai puțin
decât zero, ceea ce am spus în caietul de sarcini a problemei ar trebui să
să nu fie permis, pentru că ne dorim doar valori non-negativ, atunci ar trebui să
doar întoarce false imediat.
Deci, unele relativ ușor eroare de verificare.
Dacă totuși doriți să adăugați că reale număr, ai avut de a face un pic de
gândire aici.
Și acest lucru este în cazul în care este un pic enervant mental, pentru că trebuie să
dau seama cum să se ocupe de curbat.
>> Dar germenul a ideii de aici care e de interes pentru noi este că curbat
implică de multe ori aritmetică modulară și operatorul mod, partea de procente,
unde poti sa te duci la o valoare mai mare înapoi la zero și apoi unu și doi și
trei și apoi înapoi în jurul la zero, unul, doi, trei și așa mai departe
din nou și din nou.
Deci, modul în care ne propunem a face acest lucru este pe care noi vrem să indice în
matrice numit numere în cazul în care întregi noastre minți.
Dar pentru a ajunge acolo, ne-o dorim în primul rând să facă indiferent de dimensiunea cozii este însă
apoi se adaugă că, indiferent de față de lista este.
Și efectul de care este de a ne pune la poziția corectă în coada de așteptare și
nu presupune că prima persoană în linie este la început, pe care el sau
ea absolut ar fi dacă ne-am Au fost, de asemenea, trecerea de toată lumea.
Dar vom crea doar locul de muncă pentru noi dacă am luat
această cale special.
>> Astfel încât să putem păstra relativ simplu.
Noi nu trebuie să ne amintim că ne-am a adăugat un int la coada.
Și apoi ne vom întoarce adevărat.
Între timp, în dequeue, ne-am întrebat să faceți următoarele.
Aplicarea acesteia în așa fel încât să dequeues, că este elimină și se întoarce,
int în față de coadă.
Pentru a elimina int, este suficient să-l uite.
Nu aveți nevoie pentru a trece peste bit sale.
Deci, este încă de fapt acolo.
La fel ca datele de pe un hard-disk, suntem doar ignorând faptul
care e acum acolo.
Iar dacă q este gol, ar trebui să ne în loc să se întoarcă negativ 1.
Deci, acest lucru se simte arbitrar.
De ce reveni negativ 1 în loc de fals?
Da.
>> Audiența: Q este stocarea valori pozitive.
Din moment ce stocați doar valori pozitive în q, negativ este o eroare.
>> David J. MALAN: OK, adevărat.
Așa că suntem doar stocarea pozitiv valori sau de zero, atunci este bine să
întoarce o valoare negativă ca o santinelă valoare, un simbol special.
Dar tu rescrie istoria acolo, pentru că motivul pentru care suntem doar
revenind valori ne-negative este pentru că vrem să
au o valoare santinelă.
Deci, mai precis, de ce nu doar return false în caz de erori?
Da.
>> Audiența: Ai reușit pentru a reveni un întreg.
>> David J. MALAN: Exact.
Și acest lucru este în cazul în care C devine destul de constrângere.
Dacă spui că te duci pentru a reveni un int, ai
pentru a reveni un int.
Nu puteți obține de lux și începe revenirea un bool sau un flotor sau un
șir sau ceva de genul asta.
Acum, între timp, JavaScript și PHP și alte limbi pot, de fapt,
te-ai întoarce diferit tipuri de valori.
Și care poate fi de fapt util, în cazul în care ai putea întoarce int pozitive, zerouri,
int negative sau fals sau nul chiar pentru a semnifica eroare.
Dar nu avem acel versatilitate în C.
>> Deci, cu dequeue, ceea ce ne-am propune să faceți este să -
>> ROB BOWDEN: Puteți reveni false.
Este doar că este fals hash define false la zero.
Deci, dacă te vei întoarce false, revenind la zero.
Și zero este un lucru valabil în coada noastră, în timp ce negativ 1 nu este cazul
fals sa întâmplat să fie negativ 1.
Dar nu ar trebui să mai trebuie să știe că.
>> David J. MALAN: Asta-i de ce nu l-am spus.
>> ROB BOWDEN: Dar nu era adevărat că nu se poate întoarce false.
>> David J. MALAN: Sigur.
Deci dequeue, observa vom accepta anula ca argument.
Și asta pentru că noi nu suntem trece nimic inch
Vrem doar pentru a elimina elementul în fruntea cozii.
Deci, cum am putea merge despre a face acest lucru?
Ei bine, în primul rând, hai sa facem acest lucru verificare bun-simț rapid.
În cazul în care dimensiunea coada este 0, nu există nici o lucrare de făcut.
Întoarce negativ 1.
Efectuat.
Deci, asta e câteva linii de programul meu.
Deci, doar patru linii rămân.
>> Deci, aici am decis să decrementa dimensiunea.
Și decrementare dimensiunea efectiv înseamnă că am uitat
ceva este acolo.
Dar trebuie, de asemenea, pentru a actualiza în cazul în care față a numerele sunt.
Deci, pentru a face acest lucru, am nevoie de de a face două lucruri.
Trebuie în primul rând să-și amintească ceea ce numărul este în fruntea cozii,
pentru că am nevoie să se întoarcă chestia aia.
Așa că nu vreau să uit accidental despre ea și apoi suprascrie.
Mă duc să-mi amintesc la un int.
>> Și acum, vreau să actualizeze q.front să fie q.front +1.
Deci, dacă aceasta a fost prima persoană din linie, acum, vreau să fac, plus 1 la
punct la următoarea persoană în linie.
Dar trebuie să se ocupe de asta curbat.
Și dacă capacitatea este o constantă la nivel mondial, care va permite-mi să vă asigurați
ca am punctul de la ultima persoană în linie, operațiunea modulo va aduce
mă înapoi la zero la fata de coada.
Și care se ocupă de Manșeta aici.
Și apoi m-am proceda pentru a reveni n.
>> Acum, strict vorbind, nu am făcut- Trebuie să declare n.
Nu am avut să-l apuca și păstrați-l temporar, deoarece valoarea este
încă acolo.
Așa că am putea face doar dreptul de aritmetică pentru a reveni fostul șef
a cozii.
Dar am simțit că acest lucru a fost mult mai clar pentru a apuca de fapt int, se pune
în n, și apoi să se întoarcă că pentru motive de claritate, dar
nu strict necesar.
Psst.
Sunt toate pronunța în capul meu.
>> ROB BOWDEN: Deci, prima întrebare este problema arbore binar.
Deci, prima întrebare este, suntem având în vedere aceste numere.
Și vrem să le inserați într-un fel în aceste noduri astfel încât acesta este un
arbore binar de căutare valabil.
Deci, singurul lucru pe care să-și amintească despre arbori de căutare binare este că nu este
doar că ceea ce la stânga este mai puțin și de lucru pentru a
dreapta este mai mare.
Acesta trebuie să fie că în tot arborele de stânga este mai mică, și în tot arborele
la dreapta este mai mare.
>> Deci, dacă am pus 34 aici, în partea de sus, și apoi Am pus 20 de aici, asa ca asta e valabil atât
departe, pentru că 34 aici.
20 se merge la stânga.
Așa că e mai puțin.
Dar eu nu, atunci pot pune 59 aici, pentru că chiar dacă 59 este pe dreapta de 20,
este încă la stânga de 34.
Deci, cu care constrângere în minte, cel mai simplu mod de a rezolva, probabil, acest lucru
problema este la doar un fel dintre aceste numere -
deci 20, 34, 36, 52, 59, 106.
Și apoi introduceți cele de la stânga la dreapta.
>> Deci, 20 merge aici.
34 merge aici.
36 merge aici.
52, 59, 106.
Și tu, de asemenea, ar fi dat seama cu unele conectarea și realizarea,
oh, așteptați, eu nu au suficiente numere pentru a umple aceasta în peste aici.
Așa că am nevoie să reshift ceea ce-mi notă traseu va fi.
Dar observați că, în ultimele trei, în cazul în care ai citit de la stânga la dreapta, acesta este în
crescătoare.
>> Deci, acum, vrem să declare ceea ce struct va fi pentru
noduri în acest copac.
Deci, de ce avem nevoie într-un arbore binar?
Așa că avem o valoare de tip Int, deci o anumită valoare int.
Nu știu ce am numit l în soluția -
int n.
Avem nevoie de un pointer la copilul din stânga și un pointer la copilul din dreapta.
Asa ca va arata ca aceasta.
Și va uita de fapt, înainte de când am dublu-linked
Lista de lucruri, așa preaviz -
Am de gând să aibă de a derula toate drumul înapoi în jos la problema 11.
>> Deci observa se pare identic cu acest lucru, cu excepția ne-am întâmpla să numesc aceste
nume diferite.
Încă mai avem un număr întreg valoare și două indicii.
Este doar că în loc de tratarea indicii ca arătând spre urmatorul lucru
și lucrul anterior, vom trata indicii pentru a indica un copil stânga
și copil dreapta.
OK.
Deci, asta e nod nostru struct.
Și acum, singura funcție care avem nevoie pentru a pună în aplicare pentru aceasta este Traverse, care
vrem să mergem peste copac, tipărirea din valorile de copac, în ordine.
>> Deci, în căutarea aici, ne-ar dori pentru a imprima de 20, 34, 36, 52, 59, și 106.
Cum putem face asta?
Așa că este destul de asemănător.
Dacă ați văzut în trecut examenul problema pe care ai vrut să imprimați
întreg arborele cu virgule între totul, a fost de fapt chiar
mai ușor decât asta.
Deci, aici este soluția.
Acest lucru a fost semnificativ mai ușor dacă ai făcut-o recursiv.
Nu știu dacă cineva a încercat să o facă iterativ.
>> Dar, în primul rând, avem cazul nostru de bază.
Ce se întâmplă dacă rădăcina este nul?
Apoi, noi suntem doar de gând să se întoarcă.
Noi nu vrem să imprimați nimic.
Altfel vom traversa recursiv jos.
Imprima întreaga subarborele stâng.
Deci, tot ceea ce imprimați mai puțin decât valoarea meu actual.
Și apoi am de gând să mă imprima.
Și apoi am de gând să recurse jos meu întreaga subarbore drept, deci totul
mai mare decât valoarea mea.
Și acest lucru se întâmplă pentru a imprima totul în ordine.
Întrebări cu privire la modul în care acest fapt realizează că?
>> Audiența: Am o întrebare pe [] neauzit.
>> ROB BOWDEN: Deci, un mod de abordare orice problemă recursiv este să ne gândim doar
despre place să vă gândiți despre toate cazurile de colt.
Deci luați în considerare că vrem să imprima tot acest copac.
Deci, tot ne vom concentra pe este acest nod special -
36.
Apelurile recursive, ne prefacem cei care doar locul de muncă.
Deci, aici, acest apel recursiv la traverse, noi fără să se mai gândească
despre asta, doar traversează stânga trei, imaginați-vă că imprimă deja 20
și 34 pentru noi.
Și când în cele din urmă ne-am recursiv apel traverse pe
dreapta, care va imprima în mod corect 52, 59, și 106 pentru noi.
>> Deci, în condițiile în care aceasta poate imprima 20, 34, și de altă parte poate imprima 52, 59, 108,
tot ce trebuie să fie capabil să facă este de imprimare noi înșine în mijlocul de care.
Deci imprima totul înaintea noastră.
Imprima noi înșine, astfel încât de imprimare nodul curent 36, printf regulat, și apoi
imprima tot după noi.
>> David J. MALAN: Acest lucru este în cazul în care recursivitate devine foarte frumos.
Este acest salt uimitor de credință în cazul în care faci cea mai mică pic de lucru.
Și apoi ai lăsat pe cineva mai face restul.
Și că altcineva este, în mod ironic, tu.
Astfel de puncte spiridus grave, în cazul în care ce derulați în sus cu privire la întrebările -
>> ROB BOWDEN: Cu privire la întrebările?
>> David J. MALAN: Și în jos un pic la numerele, nimeni nu știe unde
aceste cifre provin de la?
>> ROB BOWDEN: Nu am literalmente nici o idee.
>> David J. MALAN: Ele apar de-a lungul testul.
>> Audiența: Sunt aceleasi numere?
>> David J. MALAN: Aceste cifre.
Un ou de Paște mic.
Deci, pentru cei dintre voi vizionarea on-line la acasă, dacă ne puteți spune prin e-mail la
heads@CS50.net ce semnificația din aceste șase numere recurente sunt
de-a lungul Quiz 1, vă vom duș cu atenție uimitor la finala
prelegere și o minge de stres.
Frumos, subtil.
>> ROB Bowden: Orice ultimele întrebări despre ceva pe testul?