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?