>> 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?