DAVID J. Malan: Molt bé. Així que benvinguts a la primera Postmortem CS50 per a un concurs. Pensem que havíem inaugurar aquesta tradició aquest any. I aquesta serà una oportunitat caminar a través de la solucions al concurs. I anem a accelerar o reduir la velocitat en base sobre els interessos dels que són aquí. 

Així que vostè està probablement aquí perquè ets interessats en com vostè podria tenir o hauria d'haver respost a algunes d'aquests problemes. Llavors, per què no fer una ullada en aquesta secció primer? Per això, aconseguir cadenes. Això li va donar tres versions diferents d'un programa que era, en última instància, la intenció d'obtenir una cadena d'un usuari. Si és o no ho va fer va ser esquerra a vostè per determinar. 

I ens preguntem en la pregunta 0, suposem que aquesta versió és 1 compilat i executat. Per què podria segfault el programa? A primera vista, tots els suggeriments per què? Sí 

AUDIÈNCIA: Així que jo recordo haver vist això en un exemple anterior de veure el char * s i veient l'exploració de les s i veure perquè és un punter, com va afectar el que s'ha analitzat en? És S o l'adreça de s? 

DAVID J. Malan: OK. Bé. Així que, en última instància, la font de qualsevol problema presumiblement reduirà a aquesta variable s. I és de fet una variable. El tipus de dades d'aquesta variable és char *, el que significa que va a contenir la direcció d'un personatge. I aquí està el discerniment. Es va a contenir l'adreça de un caràcter o, més en general, la direcció del primer caràcter en tot un bloc de caràcters. 

Però el problema és que es exploració, propòsit en vida, se li dóna una adreça i se li va donar un codi de format, com% s, llegir una cadena en la part de memòria en aquesta direcció. Però com que no hi ha cap signe igual abans quin punt i coma en la primera línia de codi, perquè no ho fem realitat assignar qualsevol memòria amb malloc, ja que en realitat no assignar una matriu d'una certa mida, tot que està fent és llegir l'usuari d' entrada de teclat en algun completa valor de les escombraries, que és en si per defecte. Així que les probabilitats són que van a segfault si que la direcció no només per passar a ser un valor que es pot, de fet, escriure. Tan malament no assignar el teu record allà. 

Així que a la pregunta 1, preguntem, suposem que la versió 2 és compilat i executat. Per què podria segfault aquest programa? Així que aquest és menys buggy. I no hi ha realment només una manera òbvia en el qual pot desencadenar una violació de segment aquí. I aquesta és temàtica. Cada vegada que estem usant c en la memòria, la qual cosa podries fer per induir una violació de segment amb la versió 2? 

AUDIÈNCIA: Si utilitza aquesta entrada en una cadena que és més de 49 personatges. 

DAVID J. Malan: Exactament. Cada vegada que vegi una mica de longitud fixa quan es tracta d'una matriu, la seva radar ha d'apagar que això podria ser problemàtic si vostè no està marcant la límits d'una matriu. I aquest és el problema aquí. Encara estem usant scanf. Encara estem utilitzant% s, el que significa tractar per llegir una cadena de l'usuari. Això serà llegit en s, que, en aquest punt, que és efectivament el direcció d'un tros de memòria o el seu equivalent. És el nom d'un arranjament de personatges de la memòria. 

Però exactament això, si vostè llegeix una cadena això és més de 49, 49 perquè es necessita espai per a la barra invertida 0, vostè va a desbordar- aquest memòria intermèdia. I que podria tenir sort i ser capaç de escriure un caràcter 51a, 52a, 53a. Però en algun moment, el sistema operatiu dirà, no. Això definitivament no és la memòria se li permet tocar. I el programa es va a segfault. 

Així que, l'heurística ha de ser qualsevol temps tens de longitud fixa, té per assegurar-se que vostè està comprovant la longitud del que sigui que vostè està tractant per llegir-hi. 

AUDIÈNCIA: Així que per solucionar això, podeu han tingut una declaració de comprovar realment és la longitud que o menor que? 

DAVID J. Malan: Per descomptat. Vostè només té una condició que diu que, si el - o millor dit, que no necessàriament sap amb antelació el nombre de caràcters de la usuari va a escriure, perquè vostè té ou i la gallina. No fins que hagis llegit amb scanf Pot vostè esbrinar quant temps és. Però en aquest moment, ja és massa tard, perquè vostè ja ha llegit en algun bloc de memòria. Així com un part, els evita biblioteca CS50 aquest tema per complet, el record mitjançant l'ús de fgetc. I es llegeix un caràcter alhora, de puntetes al llarg, sabent que no pot desbordar un personatge si llegeix un a la vegada. 

El problema és amb el record getString és que hem de constantment re-size que parteix de la memòria, que és només un mal. És una gran quantitat de línies de codi per fer això. Així que una altra possibilitat seria utilitzar realment un cosí, per la de parlar, de scanf. Hi ha variants de molts d'aquests funcions que realment comproven la La longitud del nombre de caràcters que es pot llegir al màxim. I es podria especificar, no llegeixen més de 50 caràcters. Així que seria un altre enfocament, però menys complaent de les entrades més grans. 

Així que la pregunta 2 pregunta: suposem que la versió 3 és compilat i executat. Per què podria segfault aquest programa? Així que aquest és en realitat el mateix respondre, encara que es veu una mica més luxós. Estem usant malloc, que se sent com nosaltres mateixos ens estem donant més opcions. I després estem alliberant a què memòria al final. Encara és 50 bytes de memòria. Així que podríem encara tractar de llegir en 51, 52, 1000 bytes. Va a segfault per exactament la mateixa raó. 

Però hi ha una altra raó també. Quina altra cosa podria malloc retorn més la direcció d'un tros de memòria? Es podria tornar null. I perquè no estem comprovant que, podríem estar fent alguna cosa estúpid per una altra raó, i és que podríem estar dient a scanf, llegim l'entrada de l'usuari des del teclat 0 en lloc, conegut com nul. I això, també, definitivament desencadenar una violació de segment. Així que per al propòsit de la prova, ho faríem accepten cap dels com raó vàlida. Un d'ells és idèntic. Un d'ells és una mica més matisada. 

Finalment, pel que fa al programa de ús de la memòria, com fer la versió 2 i versió 3 diferencien? Així, per si serveix d'alguna cosa, hem vist una aparentment interminable subministrament de possible respostes a aquesta. I entre les respostes de la gent, el que vam ser esperant, però va acceptar una altra coses, era alguna menció de la fet que la versió 2 està utilitzant l'anomenada pila. La versió 3 utilitza la pila. I funcionalment, això en realitat no fer tot el que gran part de la diferència. Al final del dia, encara estem només aconseguir 50 bytes de memòria. 

Però aquesta va ser una de les respostes possibles que estàvem buscant. Però ja veuràs, a mesura que les seves proves de tornada de la TFS, que vam fer acceptar altres discussions sobre la seva usos dispars de memòria també. Però la pila i el munt hauria estat una resposta fàcil per anar amb. Alguna pregunta? Et dono Rob. 

ROB Bowden: Llavors el problema 4. Això és en la que calia omplir en el nombre de bytes de tots aquests diferents tipus utilitzats. Així que el primer que veiem. Assumir una arquitectura de 32 bits, com aquest aparell CS50. Així que una de les coses fonamentals sobre Arquitectures de 32 bits, que ens diu exactament el gran que un punter es va per estar en l'arquitectura. 

Així que immediatament, sabem que qualsevol punter tipus és de 32 bits o 4 bytes. Així que buscant en aquesta taula, un node * és un tipus de punter. Això serà de 4 bytes. Struct node *, això és, literalment, idèntica a l'estrella de node. Així que serà de 4 bytes. Cadena, pel que no es veu com un punter encara, però el typedef, un cadena és només un char *, que és un tipus de punter. Així que serà de 4 bytes. 

Així que aquests tres són els 4 bytes. Ara, el node i l'estudiant són una mica més complicat. Així que buscant en el node i l'estudiant, veiem node com un nombre enter i un punter. I l'estudiant és de dos punters dins d'ella. Així, almenys, per al nostre cas aquí, el camí que acabem de calcular la mida de aquesta estructura s'acaba d'afegir a tot aquest és l'interior de l'estructura. 

Així que per al node, tenim un nombre enter, que és 4 bytes. Tenim un punter, que és de 4 bytes. I així un node va per ocupar 8 bytes. I el mateix per als estudiants, tenim un punter que és 4 bytes i un altre punter que és 4 bytes. Així que això acabarà sent fins a 8 bytes. Així node i l'estudiant són 8 bytes. I aquests tres són els 4 bytes. Preguntes sobre això? Sí 

AUDIÈNCIA: És que era una de 64 bits arquitectura, faria que duplicar tots ells? 

ROB Bowden: No ho faria duplicar tots ells. Així que l'arquitectura de 64 bits, que, de nou, canvis que el fonamental que un punter és ara 64 bits. Sí Així que un punter és de 8 bytes. Així que aquests que eren 4 bytes seran de 8 bytes. Un estudiant, que estava a dos punts, bé, ara que va a ser de 8 bytes, 8 bytes. Es farà 16 bytes. 

No obstant això, un node és encara 4 bytes. Així que aquest punter es va a ser de 8 bytes. Això és de 4 bytes. Així, un node només es va a ser de 12 bytes. Alguna altra pregunta sobre que un? Així que la següent, aquests són els codis d'estat HTTP. I calia descriure les circumstàncies en virtut del qual aquests podrien ser retornat a vostè. un problema que he sentit a alguns estudiants tenen és que ells van tractar de fer la errors estar a l'extrem del client. Així que quan tractem de fer la sol · licitud al servidor, alguna cosa va mal de la nostra part. Però, en general, aquests codis són sent retornat pel servidor. Pel que volem esbrinar el que està passant malament o bé al servidor que fa que aquestes coses siguin retornats. Així que Per què un servidor retorna codi d'estat 200? Alguna idea? 

Sí Així que una mica d'èxit la sol · licitud va passar. I són capaços de tornar el que em vas demanar. Així que tot estava bé. Què hi ha de 302 trobat? Sí 

AUDIÈNCIA: El servidor estava buscant pel que va sol · licitar. Però no va poder trobar-lo. Així que hi ha un error. 

ROB Bowden: Així que el cambrer va ser a la recerca del que volies. Així que buscant aquí, 302 trobats, que era capaç de trobar-lo. 

AUDIÈNCIA: Ho sento. Trobat significa que el vaig trobar. Ho sento. 

ROB Bowden: So 302 Found. El servidor és capaç de trobar el que volies. 

AUDIÈNCIA: Però no mostrar? 

ROB Bowden: La diferència entre aquest 302 i 200 és que es sap el que vol. Però no és exactament on que li volia preguntar. Així que 302 és una redirecció típic. Així que ha sol · licitat una pàgina. Sap, oh, vull tornar-això. Però això és a una adreça URL diferent. Així que bé, en realitat es vol que aquest. 

DAVID J. Malan: És una peça que va dir que vam donar vostès una redirecció funció que utilitza la funció de capçalera que, al seu torn, imprimir ubicació, còlon, i després la URL a la qual vol rebutjar l'usuari. Tot i que no va veure 302 explícitament allà, això és el que PHP màgicament inserir com encapçalat dient exactament el que va dir Rob allà - trobat. Però veu aquí al seu lloc. 

ROB Bowden: OK. I què hi ha 403 forbidden? 

AUDIÈNCIA: Crec que és que el servidor està dient bàsicament que el client no poden accedir a la pàgina principal. 

ROB Bowden: Així que si. Bé, la resposta típica que eren esperant que és una cosa així com, els arxius no chmodded apropiadament. Això és probablement sota quines circumstàncies que els vesteix. Però hi ha una raó per la qual el client podria ser el culpable aquí. De fet, hi ha un altre codi d'estat - 401. Així que aquests són molt similars. 

401 és no autoritzat. I 403 està prohibit. I així no autoritzat exclusivament aconseguir si no estàs registrat Però accedint podria significar que està autoritzat. Però si vostè ja està connectat i vostè encara no tenen permís, també es pot obtenir prohibit. Així que si estàs connectat i no té permís, prohibit també cosa que es pot aconseguir. 

DAVID J. Malan: I el mecanisme pel que aquests problemes són generalment resolt en el servidor és a través del que comandament? Chmod, si, de fet, una de permisos emetre sobre l'arxiu o directori. 

ROB Bowden: Llavors 404 no trobat. Sí Així que a diferència de 302 en què no era exactament on vostè està demanant, però sap el que vostè vol, això, només ha ni idea del que vols. I no està sol · licitant alguna cosa vàlid. 418 Sóc una tetera i després 500 servidor intern. Llavors per què et vas treure això? 

Així segfault - Jo realment no sé la classificació estàndard per a aquest. Però si el seu codi PHP tenia alguna cosa dolent en això, en teoria, podria en realitat segfault, en aquest cas, aquest Error 500 de servidor intern, cosa que està malament amb el seu servidor de configuració. O hi ha un error de sintaxi en el codi PHP. O una cosa dolenta està passant. 

DAVID J. Malan: Vam veure segfault entre les respostes d'algunes persones. I tècnicament, podria succeir. Però això seria un PHP, el programa escrit per altres persones, en realitat segfaulted, que només si aquestes persones fotut i escriure codi amb errors en seu intèrpret ho faria PHP mateix segfault. Així que, encara que 500 és com una violació de segment en l'esperit, que és gairebé sempre el resultat d'un problema de l'arxiu de configuració amb el seu servidor web o, com va dir Rob, un error de sintaxi, com tu no la va tancar una cotització. O vostè va perdre un punt i coma en algun lloc. 

AUDIÈNCIA: Així que per al conjunt de processadors de trasllat, em pensar quan ho vaig fer una vegada que fa clic al navegador, però res va passar, que van cridar la pàgina en blanc. Però va ser a causa del codi. Crec que això va ser JavaScript, oi? 

ROB Bowden: Si. 

AUDIÈNCIA: Tant de bo error encara pujar? 

ROB Bowden: Així que vostè no ha rebut aquest error perquè tot des de la perspectiva del servidor web estava completament bé. Però vostè va sol · licitar index.html. Ha sol · licitat shuttle.js i service.js. I va ser capaç de tornar amb èxit perquè totes aquestes coses - 200. D'acord. És només quan el navegador intentar interpretar el codi JavaScript que És com, espera, això no és error de JavaScript vàlida. Alguna altra pregunta? Està bé. 

DAVID J. Malan: Així que la propera dalt era el número 11. I 11 va ser la més temible per a un munt de gent. Així que la cosa més important a tenir en compte aquí era que aquesta era, de fet, sobre una llista doblement enllaçada. Però aquest no era el mateix que l'any passat problema llista doblement enllaçada, que no et va donar l'advertiment que la llista podria, de fet, ser sense classificar. 

Així que el fet que la llista va ser sense classificar i el fet que aquesta paraula era Subratllat no estava destinat a transmetre que això és realment una simplificació en cas contrari hauria estat un problema més difícil i una més llarga. Així, un error comú aquí va ser haver posat solució de l'any passat sobre el seu ésser buscapersones i després només has de copiar cegament que a mesura que la resposta, que és el dret respondre a una pregunta diferent similars en esperit. Però les subtileses aquí van ser els següents. 

Així que un, hem declarat i un node es defineix de la manera habitual aquí. Llavors definim la llista de ser un mundial punter inicialitza a null. Llavors, aparentment, hi ha dues funcions tenim prototips per aquí, inserir i treure. I després tenim un codi d'exemple aquí de fer un munt d'insercions. I llavors li demanem que completi el aplicació de inserit a continuació en aquests de manera que s'insereix en la llista n en temps constant, també va subratllar, fins i tot si ja estan presents. 

Així que la bellesa d'ésser capaç d'inserir en la constant de temps és que implica que vostè ha de inserir el nou node en el qual? A la part davantera. Així s'elimina, per sort, almenys un dels casos que requerien fins i tot més línies de codi, com ho va fer l'any passat i fins i tot a la classe quan parlat a través d'aquest tipus de coses amb els humans i amb una mica de pseudo codi verbal. Així que en la solució aquí, anem a passar per alt a la qual acabem de tenir una visual en la pantalla. 

Cal notar que estem fent el següent. I també notar l'altra simplificació era que, fins i tot si es tracta de ja present, de manera que aquest vol dir que fins i tot si el nombre ja està allà, vostè pot només cal inserir a cegues altra còpia. I això, també, estava destinat a ser un simplificació perquè pogués centrar-se, en realitat, alguns dels més part intel · lectualment interessant i no només alguns comprovació d'errors addicional donat el temps limitat. 

Així que en aquesta solució de la mostra, destinem un punter a la mà esquerra banda aquí a un node. Ara, s'adonen que el punter, com Rob va dir, és a 32 bits. I que no conté en realitat una adreça fins que assignar la direcció. I ho fem de la mà dreta banda a través de malloc. Igual que un bon ciutadà, comprovem que malloc no és, de fet, null, pel que no creem accidentalment una violació de segment aquí. I cada vegada que utilitza malloc a la vida, ha de ser la comprovació de nuls, no sigui vostè té un error subtil. 

Després inicialitzem que nul · la per assignant n i l'anterior i el següent. I en aquest cas aquí, que inicialitza anterior a nul, perquè aquesta nova node serà el nou a partir de la cistella. Així que no hi haurà res abans d'ella. I vull afegir essencialment el llista existent al nou node entorn al costat igual a la llista en si. Però no he acabat encara. Així que si la llista en si ja existia, i hi havia almenys un node ja al lloc, si aquesta és la llista aquí i puc inserir un nou node d'aquí, assegurar-se que el meu ex node assenyala cap enrere al meu nou node, perquè aquest és, de nou, una llista doblement enllaçada. 

Així que fem una comprovació de validesa. Si la llista no és nul, si ja hi ha un o més nodes d'allà, i després afegir que de nou referència per dir-ho. I després l'última cosa que necessitem de fer és en realitat l'actualització del mundial pròpia llista de variables per assenyalar perquè el nou node. Sí 

AUDIÈNCIA: A la fletxa de punter [Inaudible] és igual a null, fa que ocupar-se de la llista perquè la llista és nul? 

DAVID J. Malan: Nope. Això és simplement que jo sigui de forma proactiva cura, ja que si aquest és el meu llista original amb potser alguns més nodes per aquí i estic inserint meu node nou per aquí, no va ser res aquí. I vull capturar aquesta idea establint anterior a nul · la en el nou node. I, presumiblement, si el meu codi és correcte i no hi ha altra manera d'inserir nodes diferents d'aquesta funció, presumiblement, encara que ja té llista un o més nodes en ell, presumiblement el llista, el primer node, tindria un punter previ de null en si. 

AUDIÈNCIA: I només un seguiment. La raó de posar punter propers iguals llista sigui que estiguis fent el punter abans esmentats que està apuntant a la següent, suposo - Jo no - simplement enumera? 

DAVID J. Malan: Exactament. I així anem realment a considerar dos casos aquí realment, tot i que la fi considerarem que no és exactament el mateix que el codi. Però en un nivell alt, si això representa la llista i aquesta és una de 32 bits punter, l'escenari més simple és que aquest és nul per defecte. I suposem que vull inserir el número 50 era el primer número. Així que vaig a seguir endavant i assignar un node, que contindrà tres camps - n, anterior i següent. 

Vaig a posar el número 50 aquí, perquè això serà n. Aquest serà el proper. I això serà anterior. I així, què he de fer en aquest cas? Bé, acabo de fer la línia 1 aquí. Punter n es fa n. Llavors jo dic, prèvia han de rebre nul. Així que això serà nul. Llavors vaig a dir a continuació es posarà la llista. 

I això només funciona bé. Aquesta és nul. I el que estic dient, el nou node del costat camp ha d'aconseguir el que sigui això. Així que posa una altra nul allà. I després l'última cosa El que faig és comprovar aquí. Si la llista no és igual a null, però és igual a null, pel que ens saltem completament. I així, tot el que faig següent és la llista obté punter, que resulta en pictòricament una imatge així. Així que aquest és un dels escenaris. 

I el que li preguntaves específicament és una situació com aquesta, on ja tenim una llista d'un sol node. I si torno en l'original plantejament del problema, la propera anem a inserir per exemple és de 34, només per En nom de la discussió. Així que vaig a simplement convenientment dibuixar això per aquí. Acabo malloced. Suposem que estic comprovant nul. 

Ara, jo vaig a inicialitzar n a ser 34. I això serà n. Aquest serà el proper. I això serà anterior. Anem a fer de que no ho vaig fer aconseguir això a l'inrevés. Arriba Anterior primer en la definició. Vaig a corregir això. Aquesta és anterior. Aquest és el següent. Tot i que aquests són idèntics, anem a mantenir constant. 

Anterior. Aquest és el següent. Així que acabo de malloced meva nota, comprovat per null, assignat 34 en el node. Aconsegueix Anterior nul. Així que això em dóna això. Següent aconsegueix llista. Així que la llista és la següent. Així que aquest és el mateix ara que aquest dibuix fletxa, de manera que apuntin a 01:00 en la mateixa. I llavors jo estic comprovant si la llista no és igual a nul. I no és aquest moment. Llavors em vaig a fer la llista anterior posa punter. 

Així que la llista anterior es PTR. Així que això té l'efecte de posar una fletxa gràfica aquí. I això està posant una mica ondulat, línies. I després, finalment, actualitzo llista per apuntar a punter. Així que ara això apunta aquest noi. I ara, farem una ràpida comprovació de validesa. 

Aquí està la llista, que és la variable global. El primer node és, de fet, 34, perquè Estic seguint la fletxa. I això és correcte perquè vull inserir al principi de la llista tots els nous nodes. El seu següent camp em porta a aquest tipus. Si segueixo endavant, em va colpejar següent és nul. Així que no hi ha més llista. Si ho cop anterior, ho entenc còpia on espero. 

Així que encara hi ha alguns indicadors, òbviament, per manipular. Però el fet que li diguessin que fer això en un temps constant que significa que només tenir un nombre finit de coses se li permet fer. I quin és aquest nombre? Pot ser que sigui un pas. Podria haver-hi dos. Podria ser 1000 passos. Però és finita, el que significa que no es pot haver algun tipus de bucle passant aquí, no hi ha repetició, no hi ha bucles. És només ha de ser línies codificades de forma rígida de codi que tenim en aquesta mostra. 

Així que el següent problema 12 ens va demanar que completar la implementació de remove a continuació d'una manera que s'elimina n de la llista en el temps lineal. Així que tens una mica més marge de maniobra ara. Vostè pot assumir que n, si està present a la llista, serà present no més d'una vegada. I això també està destinat a ser un concurs basat- supòsit simplificador, per la que si es troba al número 50 en algun lloc a la llista, no ho fa també ha de preocupar sobre de continuar iteració, buscant cada possible còpia de 50, el que acaba de delegar en alguna minúcia en un temps limitat. 

Així que amb remove, aquest era sens dubte més difícil i més codi per escriure. Però a primera vista, francament, podria ser alguna cosa aclaparador i com no hi ha manera que vostè podria tenir arribar a un qüestionari. Però si ens centrem en les etapes individuals, Esperem que aviat t'atacarà que cadascuna d'aquestes persona passos té sentit obvi en retrospectiva. Així que anem a fer una ullada. 

Així que primer, inicialitzem punter estar a punt en si. Perquè vull que el temps lineal, que els mitjans Vaig a tenir una mica de bucle. I una forma comuna per repetir les nodes d'una estructura de llista o qualsevol tipus de l'estructura iterativa és prendre un punter a la part frontal de les dades estructura i llavors simplement començar a actualitzar i caminar a la teva manera a través de l'estructura de dades. Així que faré exactament això. 

Mentre punter, el meu variable temporal, no és igual a nul · la, anem a seguir endavant i comprovar. És que tinc sort? És el camp n en el node que estic actualment mirant igual a la Nombre estic buscant? I si és així, farem alguna cosa. Ara, observi si aquesta condició envolta la totalitat següents línies de codi. Això és l'únic que m'importa - la recerca d'un nombre en qüestió. Així que no hi ha una altra cosa, el que simplifica coses conceptualment una mica. 

Però ara, em vaig adonar, i vostè podria tenir només es va adonar d'això després de pensar a través d'una mica, hi ha en realitat dues casos aquí. Un d'ells és en el qual el node està en el principi de la llista, que és un mica molest, perquè això és un cas especial, ja que cal fer front amb aquesta cosa, que és l'única anomalia. A la resta de la llista, que és la mateixa cosa. Hi ha un node anterior i següent node, el node anterior, següent node. Però aquest tipus és una mica especial si està al principi. 

Així que si el punter és igual a la llista en si, pel que si estic en el començament de la llista i he trobat n, necessito de fer un parell de coses. Un, he de canviar la llista de apuntar al següent camp, 50. Així que suposo que estic tractant per eliminar 34. Així que aquest tipus ha d'anar de distància, en un moment. 

Així que vaig a dir, la llista de aconsegueix punter següent. Bé, això és punter. Següent assenyala cap aquí. Així que això està canviant en aquesta fletxa dreta ara perquè apunti a aquest tipus aquí. Ara, recordin, tenim una variable temporal. Així que no hem deixat orfes de qualsevol node, perquè també tinc aquest tipus en el meu implementació d'remove. Així que ara, si la llista en si no és nul, He de arreglar una mica d'alguna cosa. 

Necessito ara assegurar-se que aquesta fletxa, que s'apunta prèviament 50-34, això ha de desaparèixer, perquè si jo estic tractant de desfer-se de 34 anys, 50 tenien millor no manté cap tipus de referència de nou a ella com la fletxa suggerir. Així que acabo de fer aquesta línia. Així que he acabat. Aquest cas és en realitat bastant fàcil. Tallar el cap de la llista és relativament senzill. 

Per desgràcia, hi ha una bloc molest més. Així que ara, he de considerar el cas on hi ha alguna cosa en el medi. Però no és massa terrible, excepte per a la sintaxi d'aquesta manera. Així que si no estic en el començament de la llista, estic en algun lloc en el medi. I aquesta línia aquí està dient, inici en qualsevol node estàs. Anar al camp següent del node anterior i assenyalar que en el punter. 

Farem això gràficament. Això s'està complicant. Així que si tinc camps anteriors aquí - farem això - camps aquí. Vaig a simplificar els meus punters en lloc de dibuixar un munt de coses d'anada i tornada que s'entrecreuen entre si. I ara, anem a dir que és 1, 2, 3 per bé de la discussió, fins i tot però, que no s'alinea amb el problema en qüestió. 

Així que aquí està la meva llista enllaçada. Estic intentant treure les dues d'aquesta versió particular de la història. Així que he actualitzat punter a apuntar a aquest tipus. Així que això és PTR. El assenyala aquí. Aquesta és la llista, que existeix a nivell mundial, com abans. I ell està assenyalant aquí no importa què. I ara, estic intentant eliminar dues. 

Així que si el punter està assenyalant aquí, estic seguirà, pel que sembla, el punter anterior, el que em posa en 1. Llavors jo vaig a dir que la propera camp, el que em porta a aquesta caixa aquí, va a igual punter següent. Així que si aquest punter, això és el següent. Això vol dir que aquesta fletxa necessitats perquè apunti a aquest noi. 

Així que el que aquesta línia de codi té només fer és una mica d'això. I ara, aquest és l'aspecte d'un pas en la direcció correcta. Essencialment volem tallar 2 de la mitjana d'1 i 3. Així que té sentit que volem ruta aquest punter al seu voltant. Així que aquesta línia següent és comprovar si el punter següent no és nul, no hi ha de fet algú a la dreta 2, que vol dir que també hem de fer un petit tall aquí. 

Així que ara he de seguir aquest punter i actualitzar el punter anterior sobre aquest tipus per fer una mica d'un solucionar aquí el punt aquí. I ara, això és visualment agradable. És una mica desordenat en què hi ha ningú apuntant a la 2 més. 2 estigui apuntant cap a l'esquerra. I 2 està apuntant a la dreta. Però ell pot fer el que vulgui, perquè ell està a punt de ser alliberat. I no importa el que aquests valors són més. 

El que és important és que el restant nois estan encaminant dalt i per sota d'ell ara. I de fet, això és el que fem ara. Ens punter lliure, el que significa que li diem al sistema operatiu, són benvinguts per reclamar això. I després, finalment, tornem. Else implícitament, si encara no han tornat, hem de seguir buscant. Així punter és igual punter següent només significa moure aquest tipus aquí. Moveu aquest tipus aquí. Moveu aquest tipus aquí si, de fet, no trobem el nombre estem buscant encara. 

Així que, francament, es veu completament aclaparadora, crec, en un primer moment vista, sobretot si vostè va lluitar amb això durant la prova i després veure alguna cosa com això. I vostè copet a l'esquena. Bé, no hi ha manera que pogués tenir arribar a això en el qüestionari. Però jo diria, es pot fer si es trenca cap avall en aquests individu casos i només a peu a través d'ell amb cura, tot i que, és cert, en virtut de circumstàncies estressants. 

Afortunadament, el panorama va fer tot el més feliç. Vostè pot dibuixar això en qualsevol nombre de maneres. Vostè no ha de fer l'entrecreuament cosa aquí. Vostè pot fer-ho amb recta línies els agrada. Però l'essència d'aquest problema, en en general, va ser adonar-se que la drets a la final ha de ser una mica alguna cosa com això, perquè constant de temps a entendre que segueixes jamming i s'obstrueix i es obstrueix el nous nodes al principi de la llista. Alguna pregunta? Probablement el més difícil de sens dubte les preguntes de codificació. 

AUDIÈNCIA: Així que és similar a la llista el cap en els exemples anteriors. 

DAVID J. Malan: Exactament, exactament. Només un nom diferent per una variable global. A tot el món, què? 

ROB Bowden: OK. Així que aquesta és una de les que havia d'escriure el paràgraf. Algunes persones van escriure assaigs per a aquesta pregunta. Però només ha d'utilitzar aquests sis termes per descriure el que succeeix quan intenta contactar facebook.com. Així que vaig a parlar a través del procés utilitzant tots aquests termes. Així que en el nostre navegador, teclegem facebook.com i premeu Enter. Així que el nostre navegador es construirà un HTTP sol · liciten que es va a enviar a través d'algun procés de Facebook per Facebook ens respongui amb la HTML de la pàgina. 

Llavors, quin és el procés pel que la sol · licitud HTTP en realitat arriba a Facebook? Així que, primer, hem de traduir Facebook.com. Així que li va donar el nom Facebook.com, on realment fa la petició HTTP que hagi d'anar? Així que hem de traduir Facebook.com a una adreça IP, que únicament identifiqueu màquina en realitat voleu enviar aquesta sol · licitud a. El seu ordinador portàtil disposa d'una adreça IP. Qualsevol cosa connectada amb l'Internet té una adreça IP. 

Així DNS, Domain Name System, que és el que va a manejar la traducció des facebook.com a una adreça IP que que realment desitja posar-se en contacte. Així que entrem en contacte amb els servidors DNS i per exemple, quin és facebook.com? Es diu, oh, és l'adreça IP 190.212 alguna cosa, alguna cosa, alguna cosa. Està bé. Ara, sé quina màquina Me en contacte. 

Així que vostè envia la seva sol · licitud HTTP a aquesta màquina. Llavors, com arribar a aquesta màquina? Bé, la sol · licitud va des router per rebotar router. Recordeu l'exemple de la classe, on que de fet vam veure la ruta que l' paquets van prendre quan intentem per comunicar-se. Ho vam veure saltar sobre l'Atlàntic Oceà en un moment donat o el que sigui. 

Així que l'últim port termini. Així que això és ara al teu ordinador. Pot tenir diverses coses en l'actualitat comunicar-se amb Internet. Així que puc estar corrent, per exemple, Skype. Podria ser necessari un navegador web de codi obert. Podria ser una cosa que torrenting arxius. Així que totes aquestes coses són la comunicació amb el Internet d'alguna forma. 

Així que quan l'equip rep algunes dades d'Internet, com ho fa saber quines aplicacions realment vol les dades? Com sap si aquest particular, dades és per al torrenting aplicació en oposició al navegador web? Així que aquest és el propòsit dels ports en què totes aquestes aplicacions tenen reclamar un port USB de l'ordinador. Així que el seu navegador web diu, hey, Estic escoltant al port 1000. I el seu programa torrenting està dient, Estic escoltant al port 3000. I Skype diu, estic fent servir el port 4000. 

Així que quan vostè aconsegueix algunes dades que pertany a una d'aquestes aplicacions, les dades està marcat amb el port que en realitat han de ser enviats al llarg de. Així que això diu, oh, jo pertanyo al port 1000. Sé que llavors he d'enviar aquest al costat del meu navegador web. Així que la raó és pertinent en aquest cas és que els servidors web tendeixen a escoltar al port 80. Així que quan em poso en contacte Facebook.com, estic la comunicació amb una mica de màquina. Però he de dir que el port d'aquesta màquina que vull comunicar. I els servidors web tendeixen a ser escoltant al port 80. 

Si volguessin, podrien posar de manera que les llistes com al port 7000. I després, en un navegador web, el que vaig poder escriure manualment Facebook.com: 7000 enviar la sol · licitud al port 7000 del servidor web de Facebook. 

David J. Malan: I en aquest cas, fins i tot encara que no requerim que les persones esmentar això, en aquest cas, el que el port seria la sol · licitud en realitat anar a? Intenteu-ho de nou. Exactament. No busco això, sinó que una subtilesa això és no cap, l'última. 

ROB Bowden: Així que el HTTPS, ja que és escoltar específicament per al xifrada, és al port 4430. 

Audiència: I els correus electrònics són 25, oi? 

DAVID J. Malan: Sortint correus electrònics, 25, si. 

ROB Bowden: Jo ni tan sols conec la majoria de el - tots els inferiors tendeixen a ser reservat per a les coses. Crec que tot sota 1024 està reservat. 

AUDIÈNCIA: Per què vas dir 3 era un nombre equivocat? 

ROB Bowden: Perquè en una adreça IP, hi ha quatre grups de dígits. I són de 0 a 255. Així que 192.168.2.1 és un comú adreça IP de la xarxa local. Observeu tots els que estan a menys de 255. Així que quan vaig començar amb 300, que no podria tenir estat un dels nombres. 

DAVID J. Malan: Però aquest clip ximple de - era que CSI, on tenien un nombre que era massa gran per l'adreça IP. 

ROB Bowden: Teniu alguna pregunta respecte això? El següent, el canvi tan complet en tema, però tenim aquest array PHP per les cases en el quad. I tenim una llista desordenada. I volem imprimir cada element de la llista només conté el nom de la casa. Així que tenim un bucle foreach. Així que recorda, la sintaxi és foreach matriu com a element de la matriu. Així que a través de cada iteració del bucle, casa va a prendre un dels valors dins de la matriu. 

A la primera iteració, casa serà Cabot Casa. En una segona iteració, la casa es ser Courier Casa i així successivament. Així que per a cada quad com la casa, estem només va a imprimir - també podria haver fet eco - l'element de la llista i, a continuació el nom de la casa i després tancar l'element de la llista. Les claus són opcionals aquí. 

I després també vam dir en la pregunta en si, no oblidi tancar la desordenada llista d'etiquetes. Així que necessitem per sortir de la manera PHP per tal de fer això. O podríem haver fet ressò de la tancar desordenada llista d'etiquetes. 

DAVID J. Malan: També faria bé aquí han estat la utilització d'una vella escola de bucle amb un $ i = 0 0 i l'ús dels recomptes de esbrinar la longitud del raig. És el pitjor també, només una mica més prolix. 

AUDIÈNCIA: Així que si vostè anava a [Inaudible], ho faria - M'oblido del que el llaç [inaudible] és. Et $ suport quad i? 

DAVID J. Malan: Exactament. Sí, exactament. 

ROB Bowden: Alguna cosa més? 

DAVID J. Malan: Molt bé. Les compensacions. Així que havia munts de respostes possible per a cada un d'aquests. Estàvem realment buscant per una mica de pes per un costat positiu i un inconvenient. I el número 16 va demanar, validant els usuaris ' del costat del client d'entrada, com amb JavaScript en lloc de al servidor, igual que amb PHP. Quin és un avantatge de fent del costat del client? 

Bé, una de les coses que hem proposat és que es redueix la latència, ja que no han de molestar en contacte amb el servidor, que pot trigar uns milisegons o fins i tot un parell de segons evitant que i només la validació dels usuaris d'entrada del costat del client per desencadenant un controlador en presentar i només la comprovació, va fer que escrigui alguna cosa en el nom? ¿S'escriuen alguna cosa en direcció de correu electrònic? ¿Van triar una residència d' menú desplegable? 

Vostè pot donar-los retroalimentació instantània utilitzant l'ordinador GHz o el que hagin de això és realitat en el seu escriptori. Així que és només un millor usuari experimentar normalment. No obstant això, un desavantatge de fer del costat del client validació, si ho fas sense també fer la validació al servidor és que més qualsevol que vingui de CS50 sap que només es pot enviar qualsevol dada que desitgi a un servidor de qualsevol nombre de maneres. Francament, en la majoria de qualsevol navegador, pot feu clic al voltant de la configuració i just desactivar JavaScript, el que faria, per tant, desactivar qualsevol forma de la validació. 

Però també pot ser recordar que ni tan sols jo va fer algunes coses més complexes a classe utilitzant telnet i en realitat pretenent ser un navegador mitjançant l'enviament de Get peticions a un servidor. I això certament no és usant qualsevol de JavaScript. Això només em escriure ordres en un teclat. Així que en realitat, qualsevol programador en suficient comoditat amb la web i HTTP podria enviar totes les dades que ell o ella vol a un servidor sense validació. I si el seu servidor no està també revisant, Per què em donen un nom, és això en realitat una adreça de correu electrònic vàlida, va fer trien una residència d'estudiants, que podria acabar fins a la inserció falsa o simplement dades en blanc a la base de dades, el que probablement No serà una bona cosa si que estava assumint que hi era. 

Així que aquesta és una realitat molesta. Però en, del costat del client en general validació és gran. Però significa el doble de treball. Encara que sí hi ha diversos biblioteques, biblioteques Javascript per exemple, de fer això molt, molt menys d'un mal de cap. I pot tornar a utilitzar part del codi del costat del servidor, del costat del client. Però no s'adonen que és típicament treball addicional. Sí 

AUDIÈNCIA: Així que si només dit menys segur - 

DAVID J. Malan: [Rialles] Ugh. Aquests són sempre més difícil estimats per adjudicar. 

ROB Bowden: Això faria han estat acceptats. 

DAVID J. Malan: Què? 

ROB Bowden: he creat aquest problema. Això hauria estat acceptada. 

DAVID J. Malan: Si. 

AUDIÈNCIA: Cool. 

ROB Bowden: Però nosaltres no acceptem per al primer - així, el que estàvem buscant és cosa així com que no ha de comunicar-se amb el servidor. No acceptem només més ràpid. 

AUDIÈNCIA: Què passa amb No tornar a carregar la pàgina? 

ROB Bowden: Si. Aquesta va ser una resposta acceptada. 

DAVID J. Malan: Qualsevol cosa on ens sentim que era més probable que no probable que sabies el que estaves dient que és un dur línia per dibuixar de vegades. L'ús d'una llista enllaçada lloc d'una matriu per mantenir un llista d'enters ordenats. Així que un revés que sovint citem amb vinculades llistes que van motivar la seva totalitat introducció va ser a obtenir dinamisme. Poden créixer. Poden encongir. Així que vostè no ha de passar per la pedra per crear en realitat més de memòria amb una matriu. O vostè no ha de només dir, ho sento, usuari. La matriu s'omple. Així que el creixement dinàmic de la llista. Un desavantatge però de les llistes enllaçades? 

AUDIÈNCIA: És lineal. Cerca en llista enllaçada és lineal en lloc del que entreu 

DAVID J. Malan: Exactament. Buscant en una llista enllaçada és lineal, fins i tot si és ordenada, perquè es pot Només segueix aquests molles de pa, aquests punters, des del principi de la llista fins al final. No es pot aprofitar l'accés i l'atzar, per tant, la recerca binària, encara que sigui ordenada, que podria veure amb una matriu. I també hi ha un altre cost. Sí 

AUDIÈNCIA: Memòria ineficient? 

DAVID J. Malan: Si. Bé, jo no ho faria necessàriament dir ineficient. Però li costa més memòria, perquè necessita 32 bits per a cada node per al punter addicional, en menys per a una llista vinculada individualment. Ara, si només s'està emmagatzemant nombres enters i va a afegir el punter, això és en realitat alguna cosa no trivial. El que duplica la quantitat de memòria. Però en realitat, si vostè està emmagatzemant una llista enllaçada d'estructures que podrien tenir 8 bytes, 16 bytes, encara més que això, potser és menys d'un cost marginal. Però és un cost, però. Així que qualsevol d'ells hagués estat bé com desavantatges. 

18. Ús de PHP en lloc de C per escriure un programa de línia d'ordres. Així que aquí, sovint és més ràpid utilitzar una llenguatge com PHP o Ruby o Python. Només hem d'obrir de forma ràpida un editor de text. Vostè té moltes més funcions disponibles per a vostè. PHP té la pica de la cuina de les funcions, mentre que en C, tenen molt, molt poc. De fet, els nois la coneixen per les males que no té taules hash. No ha vinculat les llistes. Si vols ells, vostè ha de aplicar per si mateix. 

Així que un avantatge de PHP o en realitat qualsevol llenguatge interpretat és la rapidesa amb el qual es pot escriure codi. No obstant això, un inconvenient, hem vist això quan batuda ràpidament una Misspeller implementació en conferència usant PHP, és que l'ús d'un llenguatge interpretat normalment és més lenta. I vam veure que demostrable amb un augmentar en el temps des de 0,3 segons a 3 segon, perquè de la interpretació que en realitat succeeix. 

Un altre avantatge és que vostè no ha de compilar. Pel que també accelera el desenvolupament dit sigui de passada, perquè no té dos passos per executar un programa. Vostè només té un. I això és bastant convincent també. Utilitzant una base de dades SQL en lloc de un arxiu CSV per emmagatzemar dades. Base de dades pel que SQL s'utilitza per pset7. Arxius CSV que no van utilitzar molt. Però el vas usar indirectament en pset7 com així parlant amb Yahoo Finance. 

Però CSV és com un arxiu d'Excel, però super simple, on les columnes són només demarcada per comes dins d'un arxiu de text d'una altra manera. I l'ús d'una base de dades SQL és una mica més convincent. És un aspecte positiu, perquè teniu les coses com seleccionar i inserir i esborrar. I s'obté, presumiblement, els índexs que MySQL i altres bases de dades, com Oracle, construir per a vostè en la memòria, la qual cosa significa que el seu selecte probablement no és serà la part superior a la inferior lineal. En realitat serà una cosa com a recerca binària o alguna cosa similars en esperit. Pel que són en general més ràpid. 

No obstant això, un desavantatge és que és només més treball. És més esforç. Vostè ha d'entendre les bases de dades. Cal configurar-lo. Vostè necessita un servidor per executar aquesta base de dades en. Cal comprendre com configurar-lo. Així que aquests són només aquests tipus de compensacions. Mentre que un fitxer CSV, pot crear amb gedit. I ja està bo per anar. No hi ha complexitat més enllà d'això. 

L'ús d'un trie en lloc d'una taula hash amb encadenament separat per emmagatzemar una diccionari de paraules que recorden de pset5. Així que una prova de cap, en teoria almenys, és el que? Constant de temps, almenys si ets hash en cada un dels individu lletres d'una paraula, com vostè podria tenir per pset5. Això podria ser cinc, sis hashes valors hash si hi ha cinc o sis lletres de la paraula. I això és bastant bo. I si hi ha un límit superior sobre com temps les seves paraules podrien ser, això és temps de fet asimptòticament constant. 

Mentre que una taula hash amb separada encadenament, el problema hi ha amb això tipus d'estructura de dades és que el rendiment dels algoritmes normalment depèn del nombre de coses ja en l'estructura de dades. I això és sens dubte el cas de cadenes, de manera que les coses més es posa en una taula hash, com més temps els cadenes van, el que significa que en el pitjor dels casos cas, el que podria estar buscant és tot el camí a l'extrem d'un d'aquestes cadenes, que efectivament recau en alguna cosa lineal. 

Ara, en la pràctica, podria absolutament ser el cas que una taula hash amb cadenes és més ràpid que un corresponent aplicació trie. Però això és per diverses raons, entre els que s'intenta utilitzar una gran quantitat de memòria que pot, de fet, les coses amb calma baix, perquè no obté bona beneficis d'una cosa que es diu l'emmagatzematge en memòria cau, on les coses que estan molt junts en la memòria es pot accedir sovint més ràpidament. I de vegades un es pot topar amb una molt bona funció hash. Fins i tot si vostè ha de perdre una mica de la memòria, és possible que, de fet, ser capaç de trobar les coses ràpid i no tan dolent com linealment. 

Així que en resum, no era necessàriament Amb qualsevol d'aquests un o fins i tot dos coses específiques que estàvem buscant. Realment res convincent com Llums i ombres en general, ens va cridar l'atenció. 

ROB Bowden: Així que pel costat bo, ho vam fer No acceptar en el seu propi "més ràpid". Vostè havia de dir alguna cosa. Fins i tot si vostè ha dit teòricament més ràpid, sabíem que classe de entenies que és 0 de 1. I taula hash, en teoria, no és 0 de 1. En esmentar res sobre el temps d'execució generalment li van posar els punts. No obstant això, "més ràpid", la majoria de les solucions de el gran tauler que es van anar intents objectivament més lent que les solucions que eren les taules hash. Per tant més ràpid en i de si mateix no és realment cert. 

DAVID J. Malan: Dom de dom dom. Probablement sóc l'únic que s'adona així és com se suposa que això ser pronunciat, oi? 

ROB Bowden: Vaig tenir en realitat ni idea. 

DAVID J. Malan: fer sentit al meu cap. 

ROB Bowden: Estic fent això. D'acord. Així que aquesta és una de les que va haver de cridar l' el diagrama similar al que podria han vist en exàmens anteriors. Així que anem a veure en això. Així que des del node HTML, tenim dos nens, el cap i el cos. Així que Branch - cap i el cos. El cap té una etiqueta de títol. Així que tenim un títol. 

Ara, l'única cosa que un munt de gent oblidar és que aquests nodes de text són elements dins d'aquest arbre. Així que aquí ens toca dibuixar com ovals per diferenciar d'aquests tipus de nodes. Però avís també aquí tenim la part superior, al mig i baix va a acabar sent els nodes de text. Així que oblidar aquells era una cosa d'un error comú. 

El cos té tres fills - aquests tres divs. Així div, div, div i després el text fills del node d'aquests divs. Això és pràcticament tot perquè les preguntes. 

DAVID J. Malan: I val la pena assenyalar, tot i que no ens aturem en elles detalls en el temps que gastem en JavaScript, que l'ordre sí, en fet, la matèria tècnicament. Així que si el cap està abans que el cos de la HTML, a continuació, hauria d'aparèixer a la esquerre del cos en el DOM real. Que la seva és, en general, només per la teva informació, cosa que es diu l'ordre del document, on sí que importa. I si estigués implementant un programa d'anàlisi, un programa que llegeixi HTML a la construcció l'arbre en la memòria, per ser honest, això és probablement el que intuïtivament fer de totes maneres - de dalt a baix, esquerra a dreta. 

ROB Bowden: Preguntes sobre això? He de fer el següent? 

DAVID J. Malan: Segur. 

ROB Bowden: OK. Així que aquest és el desbordament de memòria intermèdia pregunta atac. El més important aquí és reconèixer, així, com podria un truc adversari aquest programa perquè executi codi arbitrari? , La primera línia d'ordres per argv1 argument a aquest programa, que pot ser arbitràriament llarga. Però aquí estem utilitzant memcpy per copiar argv1, que aquí és bar. Estem passant-ho com a argument. I pel que està prenent a la barra de nom. 

Així que estem memcpying bar en aquest tampó c. Quants bytes estem copiant? Bo però molts bytes bar passa a estar utilitzant, la longitud d'aquest argument. Però c és de només 12 bytes d'ample. Així que si escrivim un argument de línia d'ordres això és més de 12 bytes, estem va a desbordar aquesta en particular tampó. Ara, com pot un adversari enganyar al programar en l'execució de codi arbitrari? 

Així que recordi que aquí principal es diu foo. I així, les anomenades principals foo. Dibuixem això. Així que tenim el nostre stack. I principal té un marc de pila a la part inferior. En algun moment, les anomenades principals foo. Bé, immediatament, les anomenades principals foo. I així foo obté el seu propi marc de pila. 

Ara, en algun moment, foo tornarà. I se'n va anar retorns foo, necessitem saber en quina línia de codi dins la qual principal van ser per tal de saber on hem de reprendre en main. Podem trucar a foo del conjunt munt de diferents llocs. Com sabem on tornar? Bé, hem de emmagatzemar aquesta part. 

Així que en algun lloc per aquí, emmagatzemem on hem de tornar a un cop retorns Foo. I aquesta és l'adreça de retorn. Llavors, com un adversari podria aprofitar d'això és el fet que aquest memòria intermèdia c s'emmagatzema, anem a dir, aquí és c. Així que tenim 12 bytes per c. Aquesta és c. I aquest és l'anell de pila de foo. Així que si l'usuari maliciós entra més bytes quals 12 o entren en una ordre argument de la línia més llarga que 12 caràcters, llavors anem a desbordar el buffer. 

Podem seguir endavant. I en algun moment, anem ara n'hi ha prou que vam començar sobreescriure aquesta adreça de retorn. Així que una vegada que sobreescriure la direcció de retorn, això vol dir que quan foo retorns, estem tornant a on sigui que el usuari maliciós està dient que per qualsevol que sigui el valor de la seva entrada, per la qual caràcters que l'usuari introdueix. I pel que si l'usuari malintencionat està sent particularment intel · ligent, que pot tenir aquesta tornar a algun lloc al printDef funció o en algun lloc de la malloc funció, en qualsevol lloc arbitrari. 

Però encara més intel · ligent és el que si té l'usuari torna a la dreta aquí. I llavors comences a executar aquests com línies de codi. Així que en aquest punt, l'usuari pot introduir el que vol en aquesta regió. I ell té el control total sobre el seu programa. Preguntes sobre això? Així que la següent pregunta és completa l' reimplementació d'foo de manera que ja no és vulnerable. 

Així que hi ha un parell de maneres que podria haver fet això. Encara tenim c només sent de longitud 12. Podries haver canviat aquesta com a part de la seva solució. També hem afegit una comprovació per Assegurança de bar no era nul. Encara que vostè no necessita que per al crèdit complet. Així que estem comprovant en primer lloc la longitud de la cadena de la barra. Si és més gran que 12, llavors en realitat no fer la còpia. Així que aquesta és una forma d'arreglar. 

Una altra manera d'arreglar és lloc de tenir c només sigui de longitud 12, que el ser de longitud strlen (bar). Una altra manera d'arreglar és que en realitat només tornar. Així que si el que s'havia desfet de tots això, si només haguessis eliminat tots línies de codi, s'hauria aconseguit tot el crèdit, ja que aquesta funció en realitat no aconseguir res. Copieu la línia d'ordres argument en alguna matriu a seu marc de pila local. I llavors la cosa està tornant. I sigui el que consumat s'ha anat. Així retorn també va ser un suficient forma d'obtenir el crèdit complet. 

DAVID J. Malan: No és l'esperit de la pregunta, però acceptable pel spec, però. 

ROB Bowden: Preguntes sobre alguna cosa d'això? L'única cosa que vostè almenys cal haver compilar codi. Així que, encara que tècnicament no està vulnerables si el seu codi no compilar, no acceptem això. No hi ha preguntes? D'acord. 

DAVID J. Malan: Voleu dir que aquest títol? 

ROB Bowden: No 

DAVID J. Malan: Així que en aquest, aquest era o bé una bona notícia o mala notícia. Això és literalment el mateix problema com el primer qüestionari. I és gairebé la mateixa problema com pset1. Però s'ha simplificat deliberadament per ser una piràmide més simple, un que pot ser resolt amb una mica iteració simple. I en realitat, el que estaven fent en aquí no era tant la lògica, degut probablement, a hores d'ara, vostè és més còmode del que eren en la setmana un per bucles o loops per què, però en realitat per esmicolar que estàs una mica a gust amb el noció que PHP no és només sobre el que de programació. En realitat, pot ser utilitzat com un llenguatge escriure programes de línia d'ordres. 

I, de fet, això és el que estàvem tractant per cridar la seva atenció. Aquest és un programa de línia d'ordres del PHP. Així codi C aquí, mentre correcta en C, no corregir per a PHP. Però el codi és realment el mateix. Si es comparen les solucions per a la Prova 0 contra la prova 1, trobareu que és gairebé idèntica, llevat de alguns signes de dòlars i per al absència d'un tipus de dades. En particular, si fem una ullada aquí, veuràs que iterem, en aquest cas, des de l'1 fins al 7. 

Podríem haver fet 0 índex. Però de vegades, crec que és just mentalment més fàcil pensar en les coses d'1 a 7. Si vols una quadra, després dos blocs, després tres, després punt, punt, punt 7. Hem j s'inicialitza a 1 i després comptar amb fins a i. I aquí tot és d'altra banda idèntic. Però, es valoren positivament un parell de coses. Et donem aquestes dues línies, aquesta primera un, tontament anomenat com un embull per Bang agut. I això només s'especifica la ruta d'accés, el carpeta, en el qual un programa pot ser trobar que voleu utilitzar interpretar aquest arxiu. 

I després la línia després que, de per descomptat, significa entrar en la manera PHP. I la línia a la part inferior significa sortir de la manera PHP. I això funciona, en general, amb llenguatges interpretats. És una mica molest si escriviu un programa en un arxiu anomenat foo.php. I llavors els seus usuaris han de simplement recordi, OK, per executar aquest programa, haurà d'escriure "foo.php espai php." Tipus molest si no una altra cosa. I també revela que el seu programa està escrit en PHP, que no és tot que il · luminant per a l'usuari. 

Així que vostè pot treure el fitxer. Php en conjunt recordar de conferència. I en realitat es pot fer. / Tal si vostè ha chmodded pel que és executable. Així chmod a + x foo hauria fet això. I si a més sumem el tinglado aquí. Però en realitat, el problema estava en impressió d'alguna cosa com això. No HTML, sense codi C sense dubte, només algunes PHP. Llavors Milo després va tornar al problema 25. I en el 25, li van donar la següent codi d'esquelet, que era un pàgina web molt simple. I la part més sucosa HTML-savi va baixar aquí, en el qual tenim a l'interior del cos un formulari que té l'ID únic de les entrades dins de les quals va ser dues entrades, una amb una idea del nom, un amb una idea de botó. 

El primer va ser el text de tipus, el segona de tipus submit. I així que li vam donar, en realitat, més ingredients del que necessitava, només per vostès tenien opcions amb què per resoldre aquest problema. No estrictament necessari totes aquestes identificacions. Però li permet resoldre de diferents maneres. I a la part superior, observi que l'objectiu era desencadenar una finestra com aquesta - Hola, Milo! - perquè aparegui al navegador utilitzant el super simple, si , La funció d'alerta no lleig. I així, en última instància, això es redueix conceptualment a l'escolta d'alguna manera per presentacions del costat del client forma , No en el costat del servidor, d'alguna manera respondre a aquesta presentació per agafant el valor que l'usuari ha escrit en el camp de nom, i després mostrar-la en el cos d'un avís. 

Així que una manera de fer això és amb jQuery, la qual es veu una mica sintàcticament desconcertant al principi. Vostè pot fer això amb codi DOM pura - document.getelement per ID. Però donem una ullada a aquesta versió. Tinc un parell d'importants línies de primera. Així que un, tenim aquesta línia, que és idèntic al que podria haver vist en, crec, form2.html de la classe a la setmana 9. I això és només dir, executar el següent codi quan el document està llest. Aquesta sent important només perquè Les pàgines HTML es llegeixen de dalt a baix, d'esquerra a dreta. 

I per tant, si vostè tracta de fer alguna cosa en el codi aquí fins a cert DOM element, alguna etiqueta HTML, que està a baix aquí, ho estàs fent molt aviat, perquè aquest té ni tan sols s'ha llegit a la memòria. Així que en dir això document.ready línia, estem dient: aquí hi ha una mica de codi, explorador. Però no executar això fins que el conjunt document està llest, que és el DOM existeix l'arbre en la memòria. Aquest és una mica més senzill, si un sintàcticament mica diferent, on jo estic dient, agafar l'element HTML l'únic identificador entrades. Això és el que l'etiqueta de hash denota, l'ID únic. I després et truco. Envia. 

Així. Presentar aquí és una funció, en cas contrari conegut com un mètode, que és a l'interior de l'objecte a la mà esquerra banda cal no em destaco. Així que si vostè pensa en les entrades com a objecte en memòria - i de fet ho és. És un node en un arbre - . Presentar mitjans quan aquesta forma amb es presenta aquest ID, executar el següent codi. No m'importa el que el nom de la funció és que estic executant. Així que aquí estic utilitzant, com abans, el que és anomenada la funció lambda o funció anònima. No és en absolut intel · lectual interessant a part que no té nom, la qual cosa està bé si només estàs mai va a cridar una vegada. I a l'interior no m'ocupo en realitat la presentació de la forma. La primera vegada que declaro una variable anomenat valor. I llavors quin és l'efecte d'aquesta destacar porció aquí ara? Què fa això a una alt nivell per a mi? 

AUDIÈNCIA: Es posa el valor que el usuari no va fer en l'HTML. Es fa que la ID i després troba el valor de la mateixa. 

DAVID J. Malan: Exactament. S'agafa el node, l'única identificador és el nom. S'obté el valor de la mateixa, la qual és, presumiblement, la qual cosa l'usuari ell o ella amb tipus. I després s'emmagatzema en què variable anomenada valor. Com acotació al marge, podria tenir també fet això una mica diferent. Totalment acceptable fent alguna cosa valor mentida var aconsegueix document.getElementById. I és per això que és una mica tediós per no utilitzar jQuery. "Name". Valor. Així que totalment acceptable. Diferents maneres de fer això. jQuery només tendeix a ser una mica més concís i definitivament més populars entre els programadors. 

Ara, estic fent una mica de seny comprovar, ja que en el problema declaració vam dir explícitament, si el usuari encara no ha escrit la seva nomenar, no mostren un avís. Però vostè pot comprovar que, amb només la comprovació de la cadena buida per a un entre cometes si hi ha res realment allà. Però si no és igual a entre cometes, Vull cridar a les alertes. I l'interessant aquí és que estem utilitzant l'operador més, que fa què en JavaScript? Concatenar. Així que és com a operador punt PHPS. La mateixa idea, una sintaxi lleugerament diferent. I només estic creant la cadena que que va veure en la captura de pantalla - Hola, això i allò altre. 

I llavors l'últim detall és el següent. Per què puc tornar fals interior d'aquesta funció en l'anonimat? 

AUDIÈNCIA: No hi ha valor. T'ho poses en forma. Només diu, si el valor no és igual a blanc, i després fer-ho. Hi havia un espai en blanc en aquesta comunicació. 

DAVID J. Malan: OK. Compte, però. No hi ha ningú més aquí. I aquest fals retorn està fora del cas de condicions. Així que això posa en relleu la línia, tornarà false, executa sense importar el que quan s'envia el formulari. Què vol tornar falsa dins d'aquest controlador d'esdeveniments, com se l'anomena, l'esdeveniment en qüestió sent la submissió? 

AUDIÈNCIA: Perquè només passa una vegada. 

DAVID J. Malan: Només passa una vegada. No del tot. Sí? 

AUDIÈNCIA: S'evita que el formulari presentar al comportament predeterminat, el que faria que la recàrrega de la pàgina. 

DAVID J. Malan: Exactament. Així que estic sobrecarregant el terme presentar aquí, perquè jo estic dient, la forma és que s'envia. Però com vostè suggereix, en realitat no és ha presentat en el veritable camí HTTP. En fer clic a Envia, causa de la nostra gestor onsubmit, estem interceptant que l'enviament de formularis per dir-ho. Llavors estem fent el nostre amb codi JavaScript. Però m'estic tornant deliberadament falsa, perquè el que jo no vull que passi 01:00 fracció de segon més tard és per a tot el formulari mateixa que es presentarà a la web servidor amb parells de valors clau, canviant l'URL a ser alguna cosa així com q = gats o el que vam fer, per exemple, a la classe. No vull que això passi, perquè no hi ha escolta del servidor per a aquest Formulari d'enviament. És purament fet en codi JavaScript. I és per això que ni tan sols tenia un atribut d'acció en la meva manera, perquè jo No pretenc que això alguna vegada al servidor. 

Així que ha de ser presentat. Però estem interceptant aquesta forma presentació i prevenir el predeterminat comportament, que és en realitat anar fins al final amb el servidor. 

AUDIÈNCIA: Així que mantenir-la en el client. 

DAVID J. Malan: Mantenir del costat del client és. Exactament dreta. El següent va ser el meu oh MySQL. 

ROB Bowden: OK. Així que aquesta primera pregunta va ser en general difícil per a la gent. Malgrat els posteriors van anar millor. Així que has de triar les dades correctes tipus per a les dues d'aquestes columnes. I tots dos tenen alguns coses sobre ells que prendre la decisió difícil. Així int no era una vàlida tipus de nombre. La raó és que un compte de 12 dígits número, un int no és prou gran com per emmagatzemar dígits en total. Així que una opció vàlida hauria estat un gran int, si per casualitat vostè coneix això. Una altra opció podria haver estat un camp de caràcters de longitud 12. Així que qualsevol d'ells hagués funcionat. Int no ho faria. 

Ara, el balanç, pensar de nou a pset7. Així que fem servir específicament decimal a emmagatzemar el valor de les accions o - 

DAVID J. Malan: Efectiu. 

ROB Bowden: Efectiu. Es va utilitzar decimals per emmagatzemar la quantitat de diners en efectiu que l'usuari té actualment. Així que la raó per la qual fem això és perquè, recordeu, flotadors. No coma flotant en precisió. No es pot emmagatzemar amb precisió els diners en efectiu valors com ens volen aquí. Així decimal és capaç de precisament botiga cosa que, per exemple, dos decimals. És per això que l'equilibri, el volem ser decimal i no surar. 

DAVID J. Malan: I també, també, encara que que podria haver estat intel · ligent en altres contextos en què pensar, potser això és una oportunitat per a un int. Vaig a seguir la pista d' coses en monedes d'un cèntim. Perquè hem demostrat explícitament el valor per defecte valor de ser 100.00, que significa que només podria ser un int. I una altra subtilesa massa amb el número era que no estava destinat ser una pregunta amb trampa. Però recordar que un int en MySQL, com en C, almenys en el aparell, és de 32 bits. I tot i que no l'esperem saber exactament quants dígits que significa, recorden que el nombre més gran pot representar potencialment amb un nombre de 32 bits és més o menys el que? 

Quin nombre és el que sempre diem? 2 a la 32, que és el que més o menys? No ha de saber amb precisió. Però més o menys és de gran ajuda en la vida. És més o menys 4 mil milions. Així que el que hem dit que un parell de vegades. Sé que he dit que un parell de vegades. I és més o menys 4 mil milions. I això és una bona regla d'or per saber. Si vostè té 8 bits, 256 és el nombre màgic. Si vostè té 32 bits, 4 MIL MILIONS més o menys. Així que si vostè acaba d'escriure una baixa de 4 milions de dòlars, veuràs que és menys dígits que 12, el que significa que no és clarament suficient expressivitat per capturar una Número de compte de 12 dígits. 

ROB Bowden: OK. Així que els altres van anar millor. Així que suposem que el banc imposa una $ 20 mensuals quota de manteniment en tots els comptes. De manera que la consulta SQL podria el banc deduir $ 20 des de cada compte, encara que que resulta en alguns saldos negatius? Així que, bàsicament, hi ha quatre principals tipus de consultes - inserir, seleccionar, actualitzar i eliminar. Llavors, què pensem que som utilitzarà aquí? Actualitzar. 

Així que anem a fer una ullada. Així que aquí estem actualitzant. Què taula estem actualitzant els comptes? Així que l'actualització dels comptes. I llavors la sintaxi diu, el que en comptes estem actualitzant? Bé, estem establint l'equilibri igual a la valor corrent de la balança de menys 20. Així que això va a actualitzar totes les files de comptes, restant $ 20 a partir del balanç. 

DAVID J. Malan: Un error molt comú aquí, tot i que de vegades ens va perdonar, era que en realitat tenen codi PHP aquí cridant a la funció de consulta o posar cometes al voltant de tot el que no necessitava ser-hi. 

ROB Bowden: Recordeu que MySQL és un llenguatge independent de PHP. Ens va passar a estar escrivint MySQL en PHP. I PHP és després enviar al servidor MySQL. Però vostè no necessita PHP per tal de comunicar-se amb un servidor MySQL. 

DAVID J. Malan: Exactament. Així que no hi ha variables amb signes de dòlar hauria de ser en aquest context. Només pot fer totes les matemàtiques dins de la pròpia base de dades. 

ROB Bowden: OK. Així que la següent. És això la propera? Sí Així que amb el que la consulta SQL podria el banc recuperar els números de compte de la seva clients més rics, els que tenen saldos superiors a 1000? Llavors, quin dels quatre tipus principals anem a voler aquí? Seleccioni. Així que volem seleccionar. Què volem per seleccionar? El que la columna és el que volem per seleccionar? Específicament Voldrem per seleccionar el nombre. Però si vostè diu l'estrella, que també acceptat. 

Així que seleccioneu el nombre del que la taula? Comptes. I llavors la condició que volem? On equilibri més gran que 1000. També acceptem més o igual. Una passada. De manera que la consulta SQL podria el banc estreta, és a dir, eliminar tots els comptes que té un saldo de $ 0? Llavors, quin dels quatre som voldrà utilitzar? Suprimeix. De manera que la sintaxi per això? Eliminar en el taula? Comptes. I llavors la condició en la qual volem eliminar - on l'equilibri és igual a zero. Així eliminar totes les files de comptes on l'equilibri és zero. Les preguntes sobre qualsevol d'ells? Vols fer cua? 

DAVID J. Malan: guia de cua. Així que en aquest, li vam donar una mica estructura familiar que hem explorat 1 poc a classe amb d'estructures, que era una dada relacionats amb l'estructura d'esperit. La diferència encara que amb una cua és que havíem de recordar que d'alguna manera era a la part davantera de la cua, en gran part perquè poguéssim fer més ús eficient de la memòria, almenys si estàvem usant una matriu. 

A causa de recordar, si tenim una matriu, si, per exemple, aquesta és la part frontal de la cua, si em fico a la cua d'aquí, i llavors algú s'interposa en línia darrere meu, darrere meu, darrere meu, i una persona passa de la ratlla, que podria, com hem vist alguns dels nostres recursos humans voluntaris a la classe, tenen tots canviar d'aquesta manera. Però, en general, havent cadascú faci cosa que no és el millor ús del temps en un programa, ja que significa que el seu algorisme s'executa en el temps d'execució asimptòtica? És lineal. 

I sento que això és una mica estúpid. Si la persona següent en la línia és el següent persona que se suposa que ha d'anar a la botiga, no tots tenen a moure junts. Simplement deixa que aquesta persona es m'arrancaven quan arribi el moment, per exemple. Així que podem estalviar una mica de temps allà. I així, per fer això, però, que els mitjans que el cap de la cua o el davant de la cua va a progressivament avançar més i més profund en la matriu i eventualment podria realment embolicar al voltant si estem utilitzant un matriu per emmagatzemar el poble en aquesta cua. Així que gairebé es pot pensar en el matriu com una circular de dades estructura en aquest sentit. 

Així que d'alguna manera ha de realitzar un seguiment de la grandària de la mateixa o en realitat el final de la mateixa i després en el qual el principi que és. Així que proposem que es declara una d'aquestes cues, anomenades q ella, només una lletra. Llavors, proposem que el front sigui inicialitzat a zero i que la mida ser inicialitzat a zero. 

Així que ara mateix, no hi ha res dins d'aquesta cua. I li demanem que completi el aplicació de posada en cua a continuació en de tal manera que la funció afegeix a N Al final de q i després retorna true. Però si q està ple o negatiu, el funció ha de retornar al seu lloc fals. I els vam donar un parell de supòsits. Però en realitat no són funcionalment rellevant, hi ha només que bool, perquè, tècnicament, bool no existir en C llevat que inclogui un determinat arxiu de capçalera. Així que això va ser només assegureu-vos que no es no és un truc pregunta tipus de coses. 

Així enqueue, vam proposar a la mostra solucions per implementar de la següent manera. Un, primer revisem la facilitat, els fruits madurs. Si la cua està plena o el nombre que vostè està tractant d'inserir és menys que zero, el que vam dir en el especificació del problema ha No es permetrà, perquè només volem valors no negatius, llavors hauria simplement tornar false immediatament. Així que alguns relativament fàcil la comprovació d'errors. Si tot i que vols afegir que real nombre, calia fer una mica de pensant aquí. I aquí és on està una mica molest mentalment, perquè cal trobar la manera d'utilitzar envoltant. 

No obstant això, el germen de la idea aquí que és de interès per a nosaltres és que la envoltant sovint implica l'aritmètica modular i l'operador mod, el costat per cent, on es pot passar d'un valor més gran de nou a zero i després d'un i dos i tres i després de tornada al voltant de zero, un i dos i tres i així successivament una i altra vegada. Així que la forma es proposa fer això és que nosaltres volem índex a la matriu anomenada números on nostres nombres enters menteixen. Però per arribar-hi, el primer que volem fer qualsevol que sigui la mida de la cua és però a continuació, afegir que qualsevol que sigui el capdavant de la llista és. I l'efecte d'això és que ens posessin en la posició correcta a la cua i No assumeixi que la primera persona de la fila és al principi, que ell o ella absolutament podria ser si també van ser canviant tots. Però això és només la creació de treball per a nosaltres si prenem aquesta ruta en particular. 

Així que podem mantenir relativament simple. Hem de recordar que acabem de afegit un int a la cua. I després simplement tornem cert. Mentrestant, en treure de la cua, li preguntem tu per fer el següent. Implementar de manera que es Retirs de cua, és a dir elimina i torna, el int a la part davantera de la cua. Per treure el int, n'hi ha prou oblidar-ho. No cal per anul · lar el seu granet de sorra. Així que és encara realment allà. Igual que les dades d'un disc dur, només estem ignorant el fet que és ara. I si q està buit, hauríem que la tornarà negatiu gener. Així que això se sent arbitrària. Per què tornar negatiu gener en lloc de la falsa? Sí 

AUDIÈNCIA: Q és l'emmagatzematge de valors positius. Atès que només emmagatzema els valors positius al q, negatiu és un error. 

DAVID J. Malan: OK, és cert. Així que pel fet que només estem emmagatzemant positiu valors o zero, llavors està bé per retornar un valor negatiu com un sentinella valor, un símbol especial. Però vostè està reescrivint la història allà, perquè la raó per la qual només estem la devolució de valors no negatius és perquè volem tenir un valor sentinella. Així que, més concretament, per què no return false en cas d'errors? Sí 

AUDIÈNCIA: Has fallat per tornar un sencer. 

DAVID J. Malan: Exactament. I aquí és on es posa C limitant bastant. Si estàs dient que et vas per tornar un int, tens per tornar un int. No es pot aconseguir la suposició i començar a retornar 01:00 bool o un flotador o corda o alguna cosa així. Ara, per la seva banda, JavaScript i PHP i alguns altres llenguatges pot, de fet, has de tornar diferent tipus de valors. I això pot ser realment útil, on vostè podria tornar ints positius, zeros, ints negatius o falsa o nul · la fins i tot per significar d'error. Però no hem de versatilitat en C. 

Així que amb treure de la cua, el que proposar de fer és - 

ROB Bowden: Vostè pot tornar false. És només que és fals de hash definir falsa a zero. Així que si vostè torna falsa, vostè està tornant a zero. I el zero és una cosa vàlida a la nostra cua, mentre que 1 no és negatiu si falsa passar a ser negatiu gener. Però vostè no ha de fins i tot necessiten saber que. 

DAVID J. Malan: Això és raó per la qual no ho vaig dir. 

ROB Bowden: Però no era cert que no es pot tornar false. 

DAVID J. Malan: Segur. Així que treure de la cua, notem que acceptem anul · lar com a argument. I això és perquè no estem passa res polz Només volem eliminar l'element a la part davantera de la cua. Llavors, com podríem anar fent això? Bé, en primer lloc, farem això comprovació de validesa ràpida. Si la mida de la cua és 0, no hi ha hi ha feina per fer. Tornar negatiu gener. Fet. Així que això és unes poques línies del meu programa. Així que només quatre línies romanen. 

Així que aquí em decideixo a disminuir la mida. I decrementar la mida eficaç vol dir que m'estic oblidant alguna cosa hi és. Però també he de actualitzar quan la part davantera dels números són. Així que per fer això, necessito de fer dues coses. Primer he de recordar el que el nombre és a la part davantera de la cua, perquè he de tornar aquesta cosa. Així que no vull oblidar accidentalment sobre això i després sobreescriure. Només recordaré en un int. 

I ara, vull actualitzar q.front a ser q.front 1. Així que si aquesta va ser la primera persona a línia, ara, vull fer més 1 a apuntar a la següent persona a la fila. Però he de manejar aquesta envoltant. I si la capacitat és una constant global, això permetrà que m'asseguri com assenyalo a l'última persona en line, l'operació de mòdul portarà em de nou a zero al principi de la cua. I que maneja l'envoltant aquí. I llavors em dedico a tornar núm. 

Ara bé, estrictament parlant, no ho vaig fer de declarar n. Jo no he de agafar i deseu temporalment, perquè el valor és segueix aquí. Així que jo podria fer el aritmètic a la dreta per tornar l'excap de la cua. Però jo sentia que això era més clar per prendre realment el int, el va posar n i, a continuació, tornar aquest per a major claredat, però no és estrictament necessari. Psst. Són tots pronunciable en el meu cap. 

ROB Bowden: Així que la primera pregunta és el problema de l'arbre binari. Així que la primera pregunta és que estem tenint en compte aquests números. I volem inserir alguna manera ells en aquests nodes tals que és un vàlida arbre de cerca binària. Així que l'única cosa que cal recordar sobre arbres binaris de cerca és que no és només que la cosa a l'esquerra és menys i el que cal el dret és més gran. Ha de ser que tot l'arbre a l'esquerra és menor, i tot l'arbre a la dreta és més gran. 

Així que si poso 34 aquí a la part superior, i després Vaig posar 20 aquí, així que això és vàlid pel que lluny, perquè 34 aquí. 20 va a l'esquerra. Així que això és menys. Però no puc després posar 59 aquí, perquè tot i que el 59 està a la dreta dels 20, encara està a la banda esquerra de 34. Així que amb aquesta limitació en ment, el de manera més fàcil probablement la solució d'aquest problema és només una espècie d'aquests nombres - de manera que el 20, 34, 36, 52, 59, 106. I a continuació, inseriu els d'esquerra a dreta. 

Així que 20 va aquí. 34 va aquí. 36 va aquí. 52, 59, 106. I també es podria haver imaginat amb alguns endollar i fer, oh, espera, jo no tinc prou números per omplir això en aquí. Així que he de reshift el que el meu nota ruta serà. Però cal notar que en els tres finals, si es llegeix d'esquerra a dreta, és a creixent. 

Així que ara, volem declarar el que el estructura serà per al nodes d'aquest arbre. Llavors, què és el que necessitem en un arbre binari? Així que tenim un valor de tipus int, de manera que un valor int. No sé el que anomenem en la solució - int n. Necessitem un punter al fill esquerre i un punter al fill dret. Així que va a tenir aquest aspecte. I va realment es veuen abans Quan et lligada doblement el Llista de coses, així que avís - Vaig a haver de desplaçar tot el camí de tornada al problema 11. 

Llavors va notar que es veu idèntica a aquesta, excepte que només passa de trucar a aquests diferents noms. Encara tenim un sencer valor i dos punters. És només que en lloc de tractar el punters com assenyalar a la següent cosa i això, estem tractant els punters per apuntar a un fill esquerre i el fill dret. D'acord. Així que aquest és el nostre node estructura. I ara, l'única funció que necessitem aplicar per això és transversal, que volem anar per sobre de l'arbre, la impressió els valors de l'arbre en ordre. 

Així que buscant aquí, ens agradaria imprimir a terme el 20, 34, 36, 52, 59, i 106. Com aconseguim això? Així que és bastant similar. Si vostè va veure en l'examen passat el problema que volia imprimir tot l'arbre amb comes entre tot, en realitat era fins i tot més fàcil que això. Així que aquí està la solució. Aquest va ser significativament més fàcil si ho va fer de forma recursiva. No sé si algú ha intentat fer-ho de forma iterativa. 

Però primer, tenim el nostre cas base. I si l'arrel és nul? Llavors només anem a tornar. No volem imprimir res. Else que anem a travessar recursiva cap avall. Imprimir tot el subarbre esquerre. Així que imprimir tot menys que el meu valor actual. I després vaig a imprimir jo mateix. I després vaig a recurse pel meu tota subarbre dret, de manera que tot més gran que el valor de la meva. I això va a imprimir a terme tot en ordre. Les preguntes sobre com aquesta realitat aconsegueix això? 

AUDIÈNCIA: Tinc una pregunta a la [inaudible]. 

ROB Bowden: Així que una manera d'acostar-se a qualsevol problema recursiu és només pensar sobre ell com vostè ha de pensar sobre tots els casos de cantonada. Així que considerem que volem imprimir tot aquest arbre. Així que tot el que anem a centrar-se en és aquest node en particular - 36. Les crides recursives, que pretenen aquells que només treballen. Així que aquí, aquesta crida recursiva a transversal, que sense tan sols pensar sobre això, només que travessa l'esquerra 3, imagino que ja s'imprimeix 20 i 34 per a nosaltres. I després, quan finalment recursiva cridar transversal a la dret, que s'imprimirà correctament 52, 59, i 106 per a nosaltres. 

Així que tenint en compte que això pot imprimir 20, 34 i l'altre pot imprimir 52, 59, 108, tot el que necessitem per ser capaç de fer és imprimir nosaltres mateixos enmig d'això. Així que imprimir tot el que tenim davant nostre. Imprimir mateixos, de manera que la impressió node actual 36, printf regular, i després imprimir tot després de nosaltres. 

DAVID J. Malan: Aquí és on la recursivitat es posa molt bonic. És aquest increïble salt de fe on vostè fa els més petits mica de treball. I després deixa que algú més ho faci la resta. I que algú més és, irònicament, vostè. Així que per punts brownie greus, si es desplaça cap amunt en les preguntes - 

ROB Bowden: En les preguntes? 

DAVID J. Malan: I una mica per els números, algú sap on aquests números vénen? 

ROB Bowden: No tinc ni idea, literalment. 

DAVID J. Malan: Apareixen durant tot el concurs. 

AUDIÈNCIA: Són els mateixos números? 

DAVID J. Malan: Aquests números. Un petit ou de Pasqua. Així que per a aquells de vostès veient en línia a casa, si pot dir-nos via correu electrònic a heads@CS50.net el que la importància d'aquests sis números que es repeteixen són al llarg de la prova 1, anem a la dutxa li amb una atenció increïble a la final conferència i una pilota anti-estrès. Niça, subtil. 

ROB Bowden: Unes últimes preguntes sobre qualsevol cosa en el concurs?