>> DAVID J. Malan: Todo ben.
Entón Benvido ao primeiro Postmortem CS50 a un quiz.
Pensamos en inaugurar esta tradición este ano.
E esta será unha oportunidade para percorrer o
solucións para o problema.
E nós imos acelerar ou desacelerar base en interese da xente aquí.
>> Entón, probablemente está aquí porque é interesado en saber como podería ter ou
debería responder a algunhas destes problemas.
Entón por que non imos dar un ollo nesta sección en primeiro lugar?
Entón, quedando cordas.
Isto deulle tres versións distintas dun programa que foi, en definitiva,
destínase a obter unha secuencia dun usuario.
Se é ou non fixo iso era á esquerda para que poida determinar.
>> E pedimos na Cuestión 0, supoñer que a versión 1 é
compilado e executado.
Por que o programa pode segfault?
A primeira vista, as suxestións por que?
É.
>> Audiencia: Entón, eu lembro de ver iso en un exemplo anterior de ollar para o
char * s e vendo a dixitalización dos s e ver porque é un punteiro, coma
iso afectou o que dixitalizada?
É S ou o enderezo de s?
>> DAVID J. Malan: Aceptar.
Boa.
Así, en definitiva, a orixe de calquera problema é, presumiblemente, vai reducir
para esa variable s.
E é de feito unha variable.
O tipo da variable de datos é char *, o que significa que vai
conter o enderezo dun personaxe.
E é aí onde reside o insight.
Vai conter o enderezo de un personaxe ou, máis xeralmente, a
enderezo do primeiro carácter todo un bloque de caracteres.
>> Pero o problema é que s dixitalización, propósito na vida, é xa un enderezo e dado
un código de formato, como% s, le unha corda para o anaco de
memoria nese enderezo.
Pero porque non hai ningún signo igual antes que no primeiro punto e coma
liña de código, porque en realidade non reservar calquera memoria con
malloc, porque iso non aconteceu realmente reservar unha matriz de certa dimensión, todos
está facendo está lendo o usuario do entrada de teclado nalgúns completo
valor de lixo, que está na s por defecto.
Así, as probabilidades son que vai se segfault que o enderezo non só así acontecer
para ser un valor que pode, de feito, gravar.
Tan mal non facer súa memoria alí.
>> Entón, na cuestión 1, pedimos, supoñer que a versión 2 é
compilado e executado.
Por que este programa pode segfault?
Entón, este é menos buggy.
E hai realmente só unha xeito evidente, onde pode
desencadear un segfault aquí.
E esta é temática.
Cada vez que estamos usando c na memoria, o que podería facer para inducir un segfault
coa versión 2?
>> Audiencia: Se usar esta entrada en unha cadea que é máis que 49
caracteres.
>> DAVID J. Malan: Exactamente.
Cada vez que ver algo fixo lonxitude cando se trata dunha matriz, o seu
radar debe ir fóra que este podería ser problemático se non está comprobando o
límites dunha matriz.
E ese é o problema aquí.
Nós aínda estamos usando scanf.
Nós aínda estamos usando% s, o que significa tratar para ler unha cadea de usuario.
Isto vai ser lido en s, o que, neste punto, é efectivamente a
dirección dun bloque de memoria ou equivalente.
É o nome dun array de caracteres de memoria.
>> Pero exactamente iso, se ler unha cadea iso é máis que 49 caracteres, 49
porque precisa de espazo para a barra invertida 0, vai rebosar
que tapón.
E pode ter sorte e poder escribir un personaxe 51, 52, 53.
Pero nalgún momento, o SO vai dicir, non.
Este definitivamente non é a memoria está autorizado a tocar.
E o programa vai segfault.
>> Polo tanto, hai, a heurística debe haber ningún tempo ten lonxitude fixa, ten
para asegurarse de que está comprobando a lonxitude de todo o que estás a
ler nel.
>> Audiencia: Entón para resolver iso, pode tiveron unha declaración comprobando realmente
é o maior lonxitude ou inferior a?
>> DAVID J. Malan: Absolutamente.
Só ten unha condición que di que, se o -
ou mellor, non necesariamente saber con antelación cantos caracteres
usuario vai escribir, porque ten ovo ea galiña.
Non ata que le-lo con scanf pode descubrir canto tempo é.
Pero nese momento, xa é tarde de máis, porque xa leu en
algún bloque de memoria.
Entón, como un aparte, os evita biblioteca CS50 esta cuestión por completo, recordo
usar fgetc.
E el le un carácter de cada vez, xunto, sabéndose virando información que
Non pode rebosar un personaxe se ler un de cada vez.
>> O problema é coa recordo é getstring que temos que constantemente re-size
que pedazo de memoria, o que é só unha dor.
É unha gran cantidade de liñas de código para facelo.
Así, outra visión sería a de feito usar un primo, de xeito
dicir, de scanf.
Existen variantes de unha morea deles funcións que realmente comprobar o
lonxitude de cantos caracteres que se pode ler como máximo.
E pode especificar, non lea máis de 50 caracteres.
Así que sería outra visión, pero menos que acomodan de entradas máis grandes.
>> Entón pregunta 2 pregunta, supoña que a versión 3 é compilado e executado.
Por que este programa pode segfault?
Entón, este é realmente o mesmo responder, a pesar
parece un pouco afeccionado.
Estamos a usar malloc, que se sente como estamos dando máis opcións.
E entón nós estamos liberando que memoria ao final.
Aínda é só 50 bytes de memoria.
Así, poderiamos tentar ler en 51, 52, 1000 bytes.
Vai para segfault exactamente polo mesmo motivo.
>> Pero hai outra razón.
Que máis podería malloc retorno alén o enderezo de un bloque de memoria?
Podería volver nulo.
E por que non estamos comprobando que, poderiamos estar facendo algo
estúpido por outra razón, que é o que poderiamos estar dicindo scanf, lea
a entrada do usuario a partir do teclado a 0 local, aka nulo.
E que, ademais, será definitivamente desencadear un segfault.
Así, para o propósito da proba, teriamos aceptar un destes como un
razón válida.
Unha é idéntica.
Un deles é un pouco máis sutil.
>> Finalmente, no que se refire ao programa de uso de memoria, como é que a versión 2 e
versión 3 difiren?
Así, por que paga a pena, vimos un oferta aparentemente infinita de posible
respostas a esta.
E entre as respostas das persoas, o que eramos esperando, pero aceptamos outras
cousas, era unha mención ao feito de que a versión 2 é utilizar
a pila de chamada.
Versión 3 está a usar o heap.
E funcionalmente, iso realmente non facer todo o que moita diferenza.
Ao final do día, aínda estamos quedando 50 bytes de memoria.
>> Pero isto era unha das posibles respostas que estabamos mirando.
Pero vai ver, como comeza o seu quizzes arredor do TF, que fixemos
aceptar outras discusións sobre a súa usos distintos de memoria tamén.
Pero pila e pila sería unha resposta fácil para ir con el.
Algunha pregunta?
Eu darlle Rob.
>> ROB BOWDEN: Entón problema 4.
Esta é a única en que tiña que cubrir o número de bytes de todos
estes tipos utilizados.
Entón o primeiro que vemos.
Supoñamos unha arquitectura de 32 bits, como este aparello CS50.
Entón, unha das cousas fundamentais sobre Arquitecturas de 32 bits, que nos di
exactamente como un gran punteiro vai estar na arquitectura.
>> Entón, inmediatamente, sabemos que calquera punteiro tipo é de 32-bits ou 4 bytes.
Entón, ollando para esta táboa, unha nodo * é un tipo de punteiro.
Isto vai ser de 4 bytes.
Nó struct *, isto é literalmente idéntica á estrela no.
E así que será de 4 bytes.
Cadea, polo que non se parece un punteiro aínda, pero o typedef, un
cadea é só un char *, que é un tipo de punteiro.
Entón, iso será de 4 bytes.
>> Entón, eses tres son os 4 bytes.
Agora, nó e alumno son un pouco máis complicado.
Entón, mirando para nós e alumno, podemos ver como un enteiro e un punteiro.
E estudante é de dous punteiros no interior do mesmo.
Así, polo menos para o noso caso aquí, o xeito no que que acabamos o cálculo do tamaño da
esta estrutura é só sumar todo que está dentro da estrutura.
>> Entón, para nós, temos un número enteiro, que é de 4 bytes.
Temos un punteiro, que é de 4 bytes.
E así, un nodo está a suceder para ocupar 8 bytes.
E do mesmo xeito para o alumno, temos un punteiro que é 4 bytes e outro
punteiro que é 4 bytes.
Entón iso vai acabar sendo 8 bytes.
Entón nó e alumno son 8 bytes.
E estes tres son as 4 bytes.
Preguntas sobre iso?
Si
>> Audiencia: É que era un de 64 bits arquitectura, que sería
dobrar todos eles?
>> ROB BOWDEN: Non sería dobrar todos eles.
Así, a arquitectura de 64 bits, que, unha vez máis, cambios que cousa fundamental que a
punteiro é agora 64 bits.
É.
Así, un punteiro é de 8 bytes.
Entón, eses que foron 4 bytes van ser 8 bytes.
Un estudante, que era dous punteiros, ben, agora que vai
ser de 8 bytes, 8 bytes.
Vai facer 16 bytes.
>> Pero un nodo aínda é de 4 bytes.
Polo tanto, este punteiro vai para ser de 8 bytes.
Este é 4 bytes.
Así, un nodo está indo só ser de 12 bytes.
Calquera outras preguntas sobre este?
Entón o seguinte, estes son os códigos de estado de HTTP.
E tiña que describir as circunstancias de conformidade co cal estes puideron
ser devolto a vostede.
un problema que eu oín algúns alumnos teño é que intentaron facer o
erros de estar ao final do cliente.
Entón, cando tentamos facer a solicitude ao servidor, algo correr
mal na nosa fin.
Pero, xeralmente, eses códigos son sendo devolto polo servidor.
Entón, queremos descubrir o que está a suceder correcto ou errado no servidor que
fai que estas cousas a seren devoltos.
Entón, por que un servidor regresa código de estado 200?
Calquera pensamentos?
>> É.
Entón, algo sobre éxito a solicitude pasou.
E son capaces de voltar todo o que pediu.
Entón, todo estaba ben.
E sobre 302 encontrados?
É.
>> Audiencia: O servidor estaba buscando para o que solicitou.
Pero non puido atopalo.
Polo tanto, hai un erro.
>> ROB BOWDEN: Entón, o servidor foi ollando para o que quería.
Entón, só de ollar aquí, 302 atopados, foi capaz de atopalo.
>> Audiencia: Eu sinto moito.
Atopou significa que fixeron atopalo.
Sentímolo.
>> ROB BOWDEN: Entón 302 atopado.
O servidor é capaz de atopar o que quería.
>> Audiencia: Pero non é amosar-lo?
>> ROB BOWDEN: A diferenza entre este 302 e 200 é que
sabe o que quere.
Pero non é exactamente onde quería preguntar.
Así, 302 é unha redirección típico.
Así que solicitou unha páxina.
Sabe, oh, quero para devolverlle isto.
Pero iso é en unha URL diferente.
Entón, hey, o que realmente quere iso.
>> DAVID J. Malan: É unha peza que dixo que demos vós unha redirección
función que usei a función cabeceira que, á súa vez, impreso local,
colon, e, a continuación, a URL para o que pretender rexeitar o usuario.
Aínda que non viu 302 explicitamente alí, que é o que o PHP
Magic inserir como a cabeceira dicindo exactamente o que Rob dixo que non -
atopar.
Pero aquí en vez.
>> ROB BOWDEN: Aceptar.
Así que sobre 403 prohibido?
>> Audiencia: Eu creo que é que o servidor é basicamente dicindo que o cliente
Non pode acceder a páxina principal.
>> ROB BOWDEN: Entón, si.
Ben, a resposta típica que foron esperando algo así como, os arquivos
non son chmodded apropiadamente.
Isto probablemente é en que circunstancias viu.
Pero hai unha razón para que o cliente podería ser en falta aquí.
De feito, hai outro código de estado -
401.
Entón, estas son moi semellantes.
>> 401 non é autorizado.
E 403 é prohibido.
E así non autorizada vostede exclusivamente obter, se non está dentro do sistema Pol
Pero tamén en pode significar que está autorizado.
Pero se xa está conectado e aínda non ten permiso, logo
tamén se pode obter prohibido.
Entón, se está dentro do sistema e non teñen permiso, tamén está prohibido
algo que pode comezar.
>> DAVID J. Malan: E o mecanismo polo que estes problemas son normalmente
resolto no servidor é vía a orde?
Chmod, se é, realmente, unha permisos emitir o ficheiro ou directorio.
>> ROB BOWDEN: Entón 404 non atopado.
É.
Polo tanto, ao contrario 302 onde non era exactamente onde está pedindo, pero el sabe o que
quere, iso, só ten idea do que quere.
E non está pedindo algo válido.
418 Eu son un bule de té e, a continuación, 500 servidor interno.
Entón, por que pode ter isto?
>> Entón segfault -
En realidade, eu non sei a clasificación estándar para este.
Pero se o código PHP tiña algo de malo niso, en teoría, podería
realmente segfault, caso en que, este 500 erro interno do servidor, algo
está mal co seu servidor configuración.
Ou hai un erro de sintaxe no seu código PHP.
Ou algo de malo está a suceder.
>> DAVID J. Malan: Fixemos ver segfault entre as respostas de algunhas das persoas.
E, tecnicamente, isto podería ocorrer.
Pero iso sería un PHP, o programa escrito por outras persoas, en realidade,
segfaulted, que só se esta xente asneira e escribiu código buggy
seu intérprete faría Propio PHP segfault.
Así, aínda que 500 é como un segfault en espírito, é case sempre a
resultado dun problema de arquivo de configuración co seu servidor web ou, como dixo Rob,
un erro de sintaxe, como non pechar unha cotización.
Ou perdeu un punto e coma nalgún lugar.
>> Audiencia: Así, para o pset Shuttle, I creo que cando eu fixen iso xa prema no
navegador, pero nada veu á tona, o que eles chamaron páxina branca.
Pero foi a causa do código.
Creo que foi JavaScript, non?
>> ROB BOWDEN: Yeah.
>> Audiencia: Será que o erro aínda subir?
>> ROB BOWDEN: Entón non chegaría este erro, porque todo
do punto de vista do servidor web estaba completamente ben.
Pero pediu index.html.
Solicitou shuttle.js e service.js.
E foi capaz de volver correctamente a vostede todas esas cousas -
200.
Aceptar.
É só cando o navegador intentou interpretar o código JavaScript que
é como, espera, iso non é erro de JavaScript válido.
Algunha pregunta?
Todo ben.
>> DAVID J. Malan: Entón a próxima si era o número 11.
E 11 foi o máis asustado para unha morea de xente.
Entón, a cousa máis importante a notar aquí era que este era, de feito, sobre
unha lista dobremente vinculada.
Pero este non era o mesmo que o do ano pasado problema lista dobremente ligada,
o que non darlle a excepción de que a lista podería, de feito, ser indiferenciados.
>> Así, o feito de que a lista foi indiferenciados eo feito de que esta palabra era
subliñado non estaba destinado a transmitir que esta é realmente unha simplificación
do que doutra forma sería un problema máis reto
e un máis longo.
Así, un erro común aquí foi colocar solución do ano pasado sobre o seu un
pager e despois é só copiar cegamente que abaixo como a resposta, que é o dereito
responder a unha pregunta distinta semellante en espírito.
Pero as sutilezas aquí foron como segue.
>> Entón, un, temos un nó declarado e definido da forma usual aquí.
Logo definimos lista de ser un mundial punteiro inicializar como nulo.
Entón, ao parecer, hai dúas funcións temos prototipos para aquí, inserción
e eliminar.
E entón temos un código de exemplo aquí de facer unha chea de insercións.
E, entón, pedir-lle para completar a implementación de inserción baixo de tal
un xeito que inserir n na lista en tempo constante, tamén salientou,
aínda que xa está presente.
>> Así, a beleza de ser capaz de inserir na constante de tempo é que implica
que ten que introducir o novo nó de onde?
Na parte de diante.
Así, el elimina, por sorte, polo menos un dos casos que adoitaban requirir
aínda máis liñas de código, como o fixo o ano pasado, e mesmo na clase cando
Falamos por este tipo de cousas cos seres humanos e con algúns
pseudo código verbal.
Así, na solución aquí, imos saltar para que só para ter un na visuais
a pantalla.
>> Teña en conta que nós estamos facendo o seguinte.
E tamén entender a outra simplificación foi a de que, aínda que sexa
xa está presente, entón iso significa que, aínda que o número xa está aí, pode
cegamente inserir outro copia do mesmo.
E que, ademais, foi deseñado para ser un simplificación, de xeito que podería
centrar, en realidade, algúns dos máis parte intelectualmente interesante e
non só algúns erros adicional comprobación dado o tempo limitado.
>> Así, nesta solución de mostra, alocamos un punteiro na man esquerda
banda aquí a un nodo.
Agora entendo que punteiro, coma Rob dixo, é de só 32 bits.
E realmente non conteñen un enderezo ata que
asignar-lle a dirección.
E facemos iso na man dereita lado vía malloc.
Como un bo cidadán, encontramos que malloc non é, en realidade, nula, de xeito que
non crear accidentalmente un segfault aquí.
E cada vez que usa malloc en vida, debe ser a verificación de nulo, para que non
ten un erro sutil.
>> Entón nós arrincar que nula por asignación de n e anterior e seguinte.
E neste caso aquí, eu inicializar anterior ao nulo, xa que esta nova
nodo será o novo comezando da miña lista.
Polo tanto, non será nada antes del.
E quero engadir, esencialmente, o lista existente para o novo nodo
asentada preto igual á lista en si.
Pero eu non acabo aínda.
Entón, se a propia lista xa existía, e houbo polo menos un nodo
xa en vigor, se esta é a lista aquí e eu introducir un novo nodo aquí, eu
Debe estar seguro de que o meu ex-nodo apunta cara atrás, para o meu novo nodo,
porque esta é, de novo, unha lista dobremente vinculada.
>> Entón, facemos un test de sanidade.
Se a lista non é nulo, se xa existe un ou máis nós de alí, entón
engadir que volta de referencia, por así dicir.
E entón a última cousa que necesitamos facer é realmente actualizar o mundial
lista de variables-se a apuntar para que o novo nodo.
É.
>> Audiencia: Na frecha de punteiro [Inaudível] é igual a nulo, o fai
xestionar a lista porque a lista é nulo?
>> DAVID J. Malan: Nope.
Isto é simplemente ser eu Proativo coidado, en que, se esta é a miña
lista orixinal con quizais algúns máis nós por aquí e eu estou introducindo meu
novo nodo aquí, non vai ser nada por aquí.
E quero capturar esa idea definindo anterior para
nulo no novo nodo.
E, presuntamente, se o meu código é correcta e non hai ningunha outra forma de introducir
ademais desta función, nós presuntamente, aínda que a lista xa ten
un ou máis nós en que, presuntamente, o lista, o primeiro nodo, tería un
punteiro anterior da propia nula.
>> Audiencia: E só un follow-up.
A razón pola que se pon punteiro próximos iguais lista é que está facendo que o punteiro
antes lista na que está a apuntar a outro, eu creo -
Non -
só lista?
>> DAVID J. Malan: Exactamente.
E así imos realmente considerar dous casos aquí realmente, aínda que o
orde, imos considera-los non é exactamente o mesmo que o código.
Pero nun nivel alto, se iso supón lista e este é un de 32 bits
punteiro, o escenario máis simple é que este é nulo por defecto.
E supoña que quero introducir o número 50 foi o primeiro número.
Entón, eu estou indo a ir adiante e reservar un nó, que vai conter
tres campos -
n, anterior e seguinte.
>> Vou poñer o número 50 aquí, porque iso vai ser n.
Este será o próximo.
E iso vai ser anterior.
E entón o que podo facer neste caso?
Ben, eu teño só a liña 1 feito aquí.
Pointer n queda n.
Eu digo, entón, anterior debe obter nulo.
Entón iso vai ser nulo.
Entón eu vou dicir a continuación vai estar lista.
>> E iso só funciona ben.
Este é nulo.
E así que eu estou dicindo, o novo nó do próximo campo debe conseguir todo o que é iso.
Así que pon outro nulo alí.
E entón o último Fago é verificar aquí.
Se a lista non é igual a cero, pero é igual a cero, de xeito que ignorar que
completamente.
E así, todo o que fago é fica próxima lista punteiro, o que resulta en pictoricamente
unha imaxe así.
Entón ese é un escenario.
>> E o que estaba preguntando sobre especificamente é unha situación como esta,
onde xa temos unha lista de un nodo.
E se eu volver a subir no orixinal enunciado do problema, o próximo imos
introducir dicir é 34, só para a causa da discusión.
Entón eu vou só convenientemente aproveitar esta aquí.
Acaba malloced.
Supoñamos que eu estou comprobando nulo.
>> Agora, eu estou indo a iniciar n ser 34.
E iso vai ser n.
Este será o próximo.
E iso vai ser anterior.
Imos ter seguro que eu non fixen obter este cara atrás.
Anterior ven en primeiro lugar na definición.
Déixeme corrixir isto.
Este é anterior.
Este é o seguinte.
Aínda que estes son idénticos, imos mantelo consistente.
>> Anterior.
Este é o seguinte.
Entón, eu acabo de malloced miña nota, revisada para nula, asignados 34 no nodo.
Anterior queda nulo.
Entón iso dáme iso.
Seguinte lista fica.
Así, a lista é esta.
Polo tanto, este é o mesmo agora como deseñar este frecha, de xeito que apunte a unha
na mesma.
E entón eu estou comprobando a lista non é igual a cero.
E non é esta vez.
Entón eu vou facer a lista anterior queda punteiro.
>> Entón lista anterior queda PTR.
Entón, iso ten o efecto de poñer unha frecha gráfica aquí.
E iso está quedando un pouco ondulado, as liñas.
E entón, finalmente, eu atualizo lista para apuntar para punteiro.
Entón agora que apunta para este cara.
E agora, imos facer unha rápida verificación de sanidade.
>> Aquí está a lista, que é a variable global.
O primeiro nodo é, en realidade, o 34, porque Estou seguindo a frecha.
E iso é correcto porque quero inserir ao principio da lista
todos os novos nós.
O seu seguinte campo me leva a este cara.
Se eu continuar, eu bati logo é nulo.
Polo tanto, non hai máis lista.
Se eu acertar anterior, recibín de volta onde eu esperar.
>> Así, aínda hai algunhas indicacións, obviamente, de manipular.
Pero o feito de que lle foi dito para facer esta en tempo constante significa que só
teñen un número finito de cousas está autorizado a facer.
E o que é ese número?
Pode ser un paso.
Pode ser dous.
Pode ser de 1.000 pasos.
Pero é finito, o que significa que non pode ter ningún tipo de Looping suceder
aquí, sen recursión sen loops.
Simplemente ten que ser liñas codificadas de código que temos nesta mostra.
>> Así, o seguinte problema 12 nos pediu completar a posta en marcha de eliminar
a continuación, de tal xeito que elimina n da lista en tempo lineal.
Entón tes un pouco máis espazo de manobra agora.
Pode asumir que non se presente na lista, estará presente
non máis que unha vez.
E que tamén pretende ser unha base-quiz hipótese simplificado, de xeito
que se atopa o número 50 en algún lugar na lista, vostede tampouco
ten que preocuparse continuando a iteración, buscando as posibles
copia de 50, que só ía devolver nalgunha minuciosa en tempo limitado.
>> Así, con retirada, este foi definitivamente máis reto e máis
código para escribir.
Pero a primeira vista, a verdade, pode ser algo esmagador e como
non hai ningunha maneira que pode ter chegar a un quiz.
Pero concentrarse nas etapas individuais, Esperemos que de súpeto
golpe-lo de que cada un deles individualmente etapas ten sentido evidente
en retrospectiva.
Entón, imos dar un ollo.
>> Entón, primeiro, nós arrincar punteiro sendo en si unha lista.
Porque quero que o tempo lineal, o que significa Vou ter algún loop.
E un xeito común de interactuar sobre o nós nunha estrutura de lista ou calquera tipo
da estrutura de forma iterativa é tomar un punteiro á fronte dos datos
estrutura e despois é só comezar a actualizar lo e camiñar seu camiño
a través da estrutura de datos.
Entón, eu vou facer exactamente isto.
>> Mentres punteiro, miña variable temporal, non é igual a cero, imos
vai adiante e confía.
Será que eu teño sorte?
É o campo n no nodo Actualmente estou mirando igual ao
número que eu estou buscando?
E se é así, imos facer algo.
Agora, teña en conta esta condición se rodea a toda
seguintes liñas de código.
Este é o único que me interesa - atopar un número en cuestión.
Polo tanto, non hai outra cousa, o que simplifica cousas conceptualmente un pouco.
>> Pero agora, podo entender, e pode que só entender iso despois de pensar
mediante un bit, hai de feito, dous casos aquí.
Unha delas é que o nodo é o inicio da lista, que é un
pouco aburrido, xa que iso é unha caso especial, porque ten que tratar
con esa cousa, que é a única anormalidade.
En calquera outro lugar na lista, é o mesmo.
Hai un nodo anterior e seguinte no, o no anterior, preto nó.
Pero este cara é un pouco especial se está no inicio.
>> Polo tanto, se o enlace é igual a lista en si, entón se eu estou no inicio da
a lista e descubrín n, eu teño para facer un par de cousas.
Un, eu teño cambiar a lista apuntar para o campo seguinte, 50.
Entón supoño que eu estou tratando de para eliminar 34.
Entón este cara ten que ir lonxe en só un momento.
>> Entón, eu vou dicir, a lista punteiro queda próximo.
Ben, este é punteiro.
Logo está a apuntar aquí.
Entón, iso está cambiando ese dereito frecha agora a ligar a este cara aquí.
Agora, lembre, temos unha variable temporal.
Entón, nós non temos ningún nodo orfo, porque eu tamén teño este cara na miña
implementación de eliminación.
Entón, agora, a lista en si non é nulo, Eu teño corrixir peixe.
>> Eu teño agora estar seguro de que esta frecha, que é previamente apuntando
50-34, este ten que ir, porque se eu estou tentando librarse
de 34, 50 é mellor non manter calquera tipo de referencia de volta a el como o
frecha suxerido.
Entón, eu só fixen esa liña.
Entón eu son feito.
Este caso é realmente moi fácil.
Decepar a cabeza da lista é relativamente simple.
>> Desafortunadamente, non é iso bloque aburrido máis.
Entón, agora, eu teño que considerar o caso onde hai algo no medio.
Pero non é terrible demais, con excepción á sintaxe como esta.
Entón, se eu non estou no inicio da lista, eu estou en algún lugar no medio.
E esta liña aquí está dicindo, inicio en calquera nodo que está.
Ir á seguinte área do nodo anterior e apuntan que o punteiro.
>> Imos facelo pictoricamente.
Isto estaba quedando complicado.
Entón, se eu teño campos anteriores aquí - imos facelo - próximos campos aquí.
Vou simplificar meus punteiros vez debuxar unha morea de
cousas e para tras cruzando uns ós outros.
E agora, imos só dicir que este é 1, 2, 3 para fins de discusión, aínda
con todo, que non se aliñan con o problema en cuestión.
>> Entón aquí vai a miña lista encadeada.
Estou tentando eliminar dous nesta determinada versión da historia.
Entón eu actualizar punteiro para estar apuntando para este cara.
Polo tanto, esta é PTR.
Está apuntando aquí.
Esta lista é, que existe globalmente como antes.
E está a apuntar aquí, non importa o que.
E agora, eu estou tentando eliminar dous.
>> Entón, se punteiro está apuntando aquí, estou vai seguir, ao parecer, a
punteiro anterior, o que me pon en 1.
Estou, entón, vai dicir que o seguinte campo, o que me trae ata este
caixa aquí, vai punteiro igual seguinte.
Polo tanto, se ese punteiro, que é o seguinte.
Isto significa que esta necesidade de frecha para apuntar a este cara.
>> Entón, o que esta liña de código ten só feito é algo diso.
E agora, que está parecendo un paso na dirección correcta.
Nós esencialmente quere cortar 2 do medio de 1 e 3.
Polo tanto, ten sentido que queremos ruta este punteiro en torno a el.
Polo tanto, esta liña seguinte é verificar se punteiro próximo non é nulo, non hai
de feito alguén para a dereita, de 2, isto significa que nós tamén temos que facer
un pouco de corte aquí.
>> Así que agora cómpre seguir esta punteiro e actualizar o punteiro anterior sobre
este cara para facer un pouco de un resolver aquí o punto aquí.
E agora, visualmente este é bo.
É un pouco confuso en que non hai ninguén apuntando para o 2 máis.
2 está a apuntar cara á esquerda.
E 2 está a apuntar cara a dereita.
Pero pode facer o que quere, porque está a piques de ser liberado.
E non importa o que estes valores son máis.
>> O que é importante é que o resto caras están reenvío anterior
e debaixo del agora.
E, de feito, iso é o que facer a continuación.
Nós punteiro libre, o que significa que dicir a sistema operativo, que é benvido
para recuperar iso.
E entón, finalmente, volvemos.
Else implicitamente, se aínda non volveu,
temos que seguir buscando.
Entón punteiro igual punteiro preto só significa mover este cara aquí.
Move este cara aquí.
Move este cara aquí, se, de feito, non atopamos o número
estamos a buscar aínda.
>> Entón, francamente, parece completamente esmagadora, eu creo, en primeiro lugar
vista, especialmente se se esforzou con iso durante a proba, a continuación, ver
algo así.
E palmadiñas nas costas.
Ben, non hai ningunha maneira que eu podería ter chegar a iso no quiz.
Pero eu diría, pode, se rompe en estes individuos
casos e só atravesa-la coidado, aínda que, en realidade, baixo
circunstancias estressantes.
>> Afortunadamente, a imaxe feita todo máis feliz.
Podería chamar iso de calquera número de formas.
Non ten que facer o entrecruzamento cousa aquí.
Podería facelo con recta liñas como esta.
Pero a esencia deste problema, en xeral, foi entender que o
imaxe, ao final, que mirar un pouco algo como isto, xa que
constante de tempo implícito que manteña tocando e tocando e tocando o
novos nós ao principio da lista.
Algunha pregunta?
Probablemente o maior reto de seguramente as preguntas de codificación.
>> Audiencia: Entón a lista é semellante ao cabeza nos exemplos anteriores.
>> DAVID J. Malan: Exactamente, exactamente.
Só un nome diferente para unha variable global.
En todo o mundo o que?
>> ROB BOWDEN: Aceptar.
Polo tanto, esta é aquela en que tiña que escribir o parágrafo.
Algunhas persoas escribiu ensaios a esta pregunta.
Pero só precisa usar estes seis termos para describir o que ocorre cando
tentar poñerse en contacto facebook.com.
Entón eu vou falar co proceso usar todos estes termos.
Así, no noso navegador, nós tecleamos facebook.com e prema Intro.
Así, o noso navegador construirá unha HTTP solicitar que enviará
a través dalgún proceso de Facebook para Facebook para responder connosco a
HTML da súa páxina.
>> Entón, o que é o proceso polo que a solicitude HTTP
realmente queda para Facebook?
Entón, primeiro, debemos traducir Facebook.com.
Entón, só recibiu o nome Facebook.com, onde realmente fai a solicitude HTTP
que ir?
Entón, necesitamos traducir Facebook.com a un enderezo IP, que unicamente
identifica o que a máquina que realmente desexa enviar esta solicitude para.
O portátil ten un enderezo IP.
Todo conectado á internet ten un enderezo IP.
>> Entón, DNS, Domain Name System, que é o que vai xestionar a tradución
do facebook.com a un enderezo IP que realmente quere poñerse en contacto.
Entón, entramos en contacto cos servidores DNS e por exemplo, o que é facebook.com?
Ela di, oh, é o enderezo IP 190,212 algo, algo, algo.
Todo ben.
Agora, eu sei que a máquina Quero entrar en contacto.
>> Entón enviar a súa solicitude HTTP sobre a máquina.
Entón como é que chegar a esa máquina?
Ben, a solicitude vai de router para router salto.
Teña en conta que do exemplo en clase, onde en que vimos a ruta que o
paquetes tomou cando tentamos para comunicarse.
Vímolo ir sobre o Atlántico Océano nun punto ou calquera outra cousa.
>> Así, o último porto prazo.
Polo tanto, esta é agora no seu computador.
Pode ter varias cousas actualmente comunicar coa Internet.
Para que eu poida estar en execución, por exemplo, o Skype.
Podería ter un navegador web aberto.
Podería ter algo que torrenting arquivos.
Entón todas estas cousas son comunicando coa
Internet de algunha maneira.
>> Así, cando o equipo recibe algúns datos a partir da internet, como o fai
sabe a aplicación realmente quere os datos?
Como é que sei que este particular datos é a
torrenting aplicación en oposición para o navegador web?
Polo tanto, este é o propósito de portos en que todas estas aplicacións teñen
afirmou un porto no ordenador.
Polo tanto, o seu navegador di, hey, Estou escoitando na porta 1000.
E o seu programa torrenting está dicindo: Estou escoitando na porta 3000.
E Skype di, eu estou usando o porto 4000.
>> Entón, cando recibe algúns datos que pertence a unha destas aplicacións, os datos
está marcado con cal porta realmente debe ser enviada ao longo.
Polo tanto, este di, oh, eu pertenzo o porto 1000.
Eu sei, entón eu teño transmita a presente xunto ao meu navegador.
Así, a razón é relevante aquí é que os servidores web tenden a
escoitar no porto 80.
Entón, cando contacte Facebook.com, eu son comunicar con unha máquina.
Pero eu teño que dicir que a porta de que máquina Quere comunicarse.
E os servidores web tenden a ser escoitando no porto 80.
>> No caso de que quixesen, poderían define-lo para que enumera como na porta 7000.
E entón nun navegador web, eu podería escribir a man Facebook.com: 7000 a
enviar a solicitude para o porto 7000 do servidor de web de Facebook.
>> DAVID J. Malan: E neste caso, mesmo aínda que non esixiu que a xente
esquecer que, neste caso, o porto que a solicitude realmente ir?
Ténteo de novo.
Exactamente.
Sen ollar para iso, pero unha sutileza que está aí ningún a última.
>> ROB BOWDEN: Entón, o HTTPS, xa que é escoita especialmente para o
cifrado, é no porto 4430.
>> Audiencia: Correo-e son de 25, non?
>> DAVID J. Malan: Saída correos electrónicos, 25, si.
>> ROB BOWDEN: Eu non sei máis de a - as máis baixos tenden a ser
reservado para as cousas.
Eu creo que todo baixo 1024 está reservado.
>> Audiencia: Por que dixo 3 é o número mal?
>> ROB BOWDEN: Por un enderezo IP, hai catro agrupacións de díxitos.
E son de 0 a 255.
Entón, 192.168.2.1 é un común enderezo IP da rede local.
Teña en conta todos estes son menos de 255.
Entón, cando comece con 300, que non podería
foi un dos números.
>> DAVID J. Malan: Pero ese clip parvo de - era CSI, onde tiveron un
número que era moi grande ao enderezo IP.
>> ROB BOWDEN: Calquera dúbida sobre iso?
A seguinte, cambio tan completa en tema, pero temos este array PHP para
as casas da quad.
E nós temos unha lista desordenada.
E queremos imprimir cada elemento da lista só contén o nome da casa.
Polo tanto, temos un loop foreach.
Entón lembre, a sintaxe é foreach matriz como elemento na matriz.
Así, en cada iteración do bucle, casa vai asumir un dos
valores dentro da matriz.
>> Na primeira iteración, casa será Cabot House.
Nunha iteración segundo, a casa vai ser Correo casa e así por diante.
Así, para cada quad como casa, estamos só vai imprimir -
tamén podería ecoado -
o elemento da lista e, a continuación, o nome da casa e logo, pechar o elemento da lista.
As claves son opcionais aquí.
>> E entón nós tamén dixo na pregunta si mesmo, lembre de pechar a
desordenadas lista de etiquetas.
Entón, necesitamos saír do modo PHP a fin de facelo.
Ou poderiamos ecoado a pechar tag lista non ordenada.
>> DAVID J. Malan: Tamén sería ben aquí ser a usar unha antiga escola para
loop cun $ i = 0 0 e usando a conta descubrir a lonxitude do raio.
Totalmente ben tamén, só algo prolixa.
>> Audiencia: Entón, se estaba indo a [Inaudível], faría -
Eu esquezo o que o loop [inaudível] é.
Vostede $ soporte quad i?
>> DAVID J. Malan: Exactamente.
Si, exactamente.
>> ROB BOWDEN: Máis algo?
>> DAVID J. Malan: Todo ben.
Trade-offs.
Así, había acios respostas posible para cada un deles.
Estabamos realmente só buscando algo convincente para un lado positivo e
un lado negativo.
E o número 16 pediu, valida os usuarios ' do lado do cliente de entrada, como con JavaScript,
en vez de na parte do servidor, como acontece con PHP.
Entón o que é un lado positivo de facendo do lado do cliente?
>> Ben, unha das cousas que propuxemos é que reducir a latencia, porque
non ten que preocuparse en contacto co servidor, o que pode levar un pouco
milisegundos ou incluso un par de segundos evitando que e só
valida a entrada do lado do cliente dos usuarios por provocando un manipulador en presentar e
só a comprobación, eles escriba algo para o nome?
Será que escribir algo no ao enderezo de correo-e?
Será que eles escollen un dormitorio de No menú desplegable?
>> Pode darlles feedback instantáneo usando o ordenador gigahertz
ou o que eles teñen que se de feito, na súa mesa.
Entón é só un usuario mellor probar normalmente.
Pero unha desvantaxe de facer do lado do cliente validación, se fai iso sen tamén
facer a validación do lado do servidor é que ninguén saíndo do CS50 sabe
que pode só enviar todos os datos que desexe para un servidor de calquera número de formas.
Francamente, na maior parte de calquera navegador, pode prema en torno ás definicións e só
desactivar o Javascript, o que, polo tanto, desactive calquera forma de
validación.
>> Pero tamén debe lembrar que, aínda que eu fixen algunhas cousas misteriosas na clase mediante
telnet e realmente finxindo ser un navegador enviando get
solicitudes para un servidor.
E iso certamente non é utilizando calquera JavaScript.
Isto é só me escribir comandos nun teclado.
Entón, realmente, calquera programador dentro suficiente confort coa web e HTTP
podería enviar todos os datos que el ou ela quere a un servidor sen validación.
E se o seu servidor non está tamén a comprobación, que me deron un nome, é
iso realmente unha dirección de correo válida, non eles escollen un dormitorio, pode acabar
se inserir teito ou só de datos en branco na súa base de datos, o que probabelmente
non vai ser bo se estabas supoñendo que estaba alí.
>> Polo tanto, esta é unha realidade desagradable.
Pero, en xeral, do lado do cliente validación é grande.
Pero isto significa que o dobre do traballo.
Aínda que exista varios bibliotecas, bibliotecas JavaScript para
exemplo, que facelo moito, moito menos dunha dor de cabeza.
E pode reutilizar parte do código do lado do servidor, do lado do cliente.
Pero non se dan conta que é tipicamente traballo adicional.
É.
>> Audiencia: Entón, se nós só dixo menos seguro -
>> DAVID J. Malan: [Risas]
Ugh.
Aqueles son sempre o máis difícil aqueles para xulgar.
>> ROB BOWDEN: Isto faría foron aceptadas.
>> DAVID J. Malan: O que?
>> ROB BOWDEN: Eu creei este problema.
Iso sería aceptado.
>> DAVID J. Malan: Yeah.
>> Audiencia: Cool.
>> ROB BOWDEN: Pero non aceptou para o primeiro -
ben, o que estabamos a buscar é algo que non ten que
comunicarse co servidor.
Non aceptamos só máis rápido.
>> Audiencia: E sobre Non actualizar a páxina?
>> ROB BOWDEN: si.
Esa foi unha resposta acepta.
>> DAVID J. Malan: Calquera cousa onde nos sentimos que era máis probable que non probable
que sabía o que eran dicindo, que é un duro
liña para deseñar algunhas veces.
Empregando unha lista ligada en vez dunha matriz para manter un
lista de enteiros ordenada.
Entón, un de cabeza, moitas veces citan con conectado listas que motivaron a súa enteira
introdución foi comeza dinamismo.
Elas poden crecer.
Poden encoller.
Entón non ten que ir a través de marcos realmente crear máis memoria
cunha matriz.
Ou non ten que dicir, desculpe, o usuario.
A matriz é cuberta.
Así, o crecemento dinámico da lista.
A desvantaxe a pesar de listas ligadas?
>> Audiencia: É lineal.
Buscando en lista ligada é linear ao contrario do que log in
>> DAVID J. Malan: Exactamente.
Buscando nunha lista ligada é lineal, aínda que sexa ordenado, porque pode
só siga estas migas de pan, estes punteiros, a partir do inicio da lista
ao fin.
Non pode usar o acceso aleatorio e, Así, busca binaria, aínda que sexa
clasificado, que podería facer un array.
E hai tamén outro custo.
É.
>> Audiencia: Memoria ineficiente?
>> DAVID J. Malan: Yeah.
Ben, eu non iría, necesariamente, dicir ineficiente.
Pero iso non lle custa máis memoria, porque precisa de 32 bits para cada
nó ao punteiro adicional, en menos a unha lista vinculada illadamente.
Agora, se está almacenando só números enteiros e está engadindo o punteiro, que é
en realidade, unha especie de non-trivial.
É duplicando a cantidade de memoria.
Pero en realidade, se está almacenando un lista ligada de estruturas que poidan ter
8 bytes, 16 bytes, aínda máis do que iso, é posible que menos
dun custo marxinal.
Pero é un custo, con todo.
Así, ou daqueles tería foi moi ben como inconvenientes.
>> 18.
Utilizando PHP en vez de C para escribir un programa de liña de comandos.
Entón, aquí, moitas veces é máis rápido usar unha linguaxe como PHP ou Ruby ou Python.
Acaba de abrir rapidamente un editor de texto.
Ten moito máis funcións dispoñibles para ti.
PHP ten a pía da cociña de funcións, mentres que en C, que
ten moito, moi pouco.
De feito, a xente sabe o xeito máis difícil que non ten táboas de hash.
Non ligaron listas.
Se quere aqueles, ten que implementar las vostede mesmo.
>> Entón, unha cabeza de PHP ou realmente calquera linguaxe interpretada é a rapidez
co cal podes escribir código.
Pero unha desvantaxe, vimos isto cando eu axiña chicoteado ata un misspeller
implantación na aula empregando PHP, é que o uso dunha linguaxe interpretada
é xeralmente máis lento.
E vimos que comprobada cun aumento no tempo de 0,3 segundos para tres
segundo, debido á interpretación que realmente acontece.
>> Outra vantaxe é que Non ten que compilar.
Por iso, tamén acelera o desenvolvemento de feito, porque non ten
dúas etapas para a execución dun programa.
Só ten un.
E así que é moi atractivo tamén.
Usando unha base de datos SQL, en vez de un ficheiro CSV para almacenar datos.
Base de datos para SQL se usa para pset7.
Ficheiros CSV non usar moito.
Pero usou indirectamente en pset7 como ben, falando con Yahoo Finance.
>> Pero CSV é como un arquivo de Excel, pero super sinxelo, onde as columnas son
só demarcado por comas dentro dun ficheiro de texto doutra forma.
E usando unha base de datos SQL está un pouco máis convincente.
É un lado positivo, porque facer as cousas como seleccionar e introducir e eliminar.
E ten, presuntamente, índices que MySQL e outros bancos de datos, como
Oracle, construír para ti a memoria, que significa que a súa elección non pode ser
será top lineal abaixo.
Realmente vai ser algo como busca binária ou algo
semellante en espírito.
Entón, son xeralmente máis rápido.
>> Pero a desvantaxe é que é só traballo.
É máis esforzo.
Ten que entender bancos de datos.
Ten que configurar-lo.
Debe dun servidor para realizar Esta base de datos en.
Debe entender como configurar-lo.
Entón, estas son só estes tipos de trade-offs.
Considerando un ficheiro CSV, pode crealo con gedit.
E está preparado para ir.
Non hai ningunha complexidade ademais.
>> Empregando un trie en vez de unha táboa hash con fío separado para almacenar unha
dicionario de palabras que lembran de pset5.
Así, un trata de cabeza, en teoría polo menos, é o que?
Constante de tempo, polo menos se é hashing en cada do individuo
letras nunha palabra, como pode ter para pset5.
Isto pode ser cinco, seis hashes hashes se hai cinco ou seis
letras da palabra.
E iso é moi bo.
E se hai un límite superior sobre o xeito no que longo das súas palabras poidan ser, que é
tempo de feito asintótica constante.
>> Considerando unha táboa hash coa separado fío, o problema alí con que
tipo de estrutura de datos é que o rendemento dos seus algoritmos normalmente
depende do número de cousas xa na estrutura de datos.
E iso é sempre o caso con cadeas, en que canto máis cousas pór
nunha táboa hash, máis tempo os cadeas de ir, o que significa que, no peor
caso, a cousa que pode estar a buscar é toda a maneira, ao final dun
destas cadeas, o que efectivamente transforma en algo lineal.
>> Agora, na práctica, é absolutamente posible ser o caso dunha táboa hash coa
cadeas é máis rápido que un correspondente implantación trie.
Pero iso é, por varias razóns, entre que son intentos usar unha morea de
memoria que pode, de feito, as cousas devagar abaixo, xa que non queda bo
beneficios dunha cousa chamada caché, onde as cousas que están xuntos
en memoria se pode acceder moitas veces máis rápido.
E ás veces pode vir ata con realmente unha boa función hash.
Aínda que ten que perder un pouco de memoria, pode, de feito, ser capaz de
atopar as cousas rápido e non tan malo como linearmente.
>> Entón, en suma, non había necesariamente con calquera un ou mesmo dous
cousas específicas que estabamos a buscar.
Realmente nada convincente como ascendentes e descendentes
xeralmente chamou a nosa atención.
>> ROB BOWDEN: Entón, para o lado positivo, fixemos non aceptar a súa propia "máis rápido". Vostede
tiña que dicir algo sobre iso.
Aínda que dixo, en teoría, máis rápido, sabiamos que tipo de entendido
que é 0 a 1.
E táboa hash, en teoría, Non é de 0 a 1.
Mencionando nada sobre tempo de execución xeralmente ten os puntos.
Pero o "máis rápido", a maioría das solucións en o gran consello que foron intentos foron
obxectivamente máis lento que as solucións que eran táboas de hash.
Así, máis rápida en si non é realmente verdade.
>> DAVID J. Malan: Don de don don.
Eu son probablemente a única que entende é así que se quere
ser pronunciado, non?
>> ROB BOWDEN: Eu tiña, en realidade, non fago idea.
>> DAVID J. Malan: Fixo sentido na miña cabeza.
>> ROB BOWDEN: Estou facendo este.
Aceptar.
Polo tanto, esta é aquela en que tiña que deseñar o diagrama semellante a podes
teño visto nos exames anteriores.
Entón imos só ollar para iso.
Entón, a partir do nó HTML, temos dous nenos, a cabeza eo corpo.
Entón, nós ramifican - cabeza e corpo.
A cabeza ten unha etiqueta title.
Polo tanto, temos un título.
>> Agora o único que unha chea de xente Esqueceu é que estes nós de texto son
elementos dentro desta árbore.
Entón aquí nós ocorrer para deseña-los como ovais para diferencialo los a partir destes
tipos de nós.
Pero teña en conta tamén aquí temos de arriba, medio e fondo vai acabar por ser
nós de texto.
Entón, esquecendo quen foi un pouco dun erro común.
>> O corpo ten tres fillos - estas tres divs.
Entón div, div, div e entón o texto fillos do nodo destes divs.
Iso é moi bonito iso para que as preguntas.
>> DAVID J. Malan: E é interesante notar, a pesar de non se debruzouse sobre estes
detalles do tempo que gastamos en JavaScript, que fai a petición, en
feito, a materia tecnicamente.
Entón, se a cabeza vén antes do corpo na HTML, a continuación, debe aparecer ao
esquerda do corpo no DOM efectivo.
Que o é, en xeral, só FYI, unha cousa chamada orde do documento, onde
iso non importa.
E se foi a posta en marcha dun parser, un programa que le HTML na construción
ata a árbore na memoria, para ser honesto, isto pode ser o que intuitivamente
facer de calquera maneira - de arriba para abaixo, esquerda a dereita.
>> ROB BOWDEN: Preguntas sobre iso?
Debo facer o seguinte?
>> DAVID J. Malan: Por suposto.
>> ROB BOWDEN: Aceptar.
Entón que é o estourido de buffer pregunta ataque.
A principal cousa a recoñecer é aquí, ben, como pode un truco adversario
este programa en execución código arbitrario?
Entón argv1, a primeira liña de comandos argumento a este programa, que se pode
arbitrariamente longo.
Pero aquí estamos usando memcpy para copiar argv1, que aquí é bar.
Estamos pasando-o como argumento.
E así está tomando na barra de nome.
>> Entón, nós estamos memcpying bar neste tapón c.
Cantos bytes estamos copiando?
Así con todo moitos bytes bar pasa a estar a usar, a lonxitude do argumento.
Pero c é de só 12 bytes de ancho.
Entón, se nós tecleamos un argumento de liña de comandos iso é máis que 12 bytes, estamos
vai rebosar esta determinado buffer.
Agora, como pode un adversario enganar o programa en execución de código arbitrario?
>> Entón recorda que aquí principal é chamar foo.
E entón chamadas principais foo.
Imos deseñar iso.
Polo tanto, temos a nosa stack.
E principal ten un cadro de pila na parte inferior.
Nalgún momento, as chamadas principais foo.
Ben, de inmediato, as chamadas principais foo.
E así foo recibe o seu propio cadro de pila.
>> Agora, nalgún momento, foo vai volver.
E foi foo retorno, o que necesitamos saber en que liña de código dentro de nós principal
estaban a fin de saber onde debemos seguir na principal.
Podemos chamar foo dun todo chea de lugares diferentes.
Como sabemos a onde volver?
Ben, necesitamos gardar isto en algún lugar.
>> Entón, en algún lugar por aquí, nós gardados onde debemos volver xa
foo retorna.
E este é o enderezo de retorno.
Entón, como un adversario pode aproveitar isto é o feito de que
este tapón c son almacenados, imos dicir, aquí é c.
Entón, nós temos 12 bytes para c.
Este é c.
E este é o anel pila de foo.
Polo tanto, se o usuario mal intencionado entra máis bytes que 12 ou eles entran nun mando
argumento de liña que é máis que 12 caracteres, entón imos
rebosar este buffer.
>> Podemos continuar.
E nalgún momento, imos lonxe o suficiente para que nós comezamos
substituír este enderezo de retorno.
Así, unha vez que substituír o enderezo de retorno, isto quere dicir que, cando foo
retorno, estamos volvendo a onde quere que o usuario mal intencionado está dicindo a el para por
o valor que el entrou, por calquera caracteres que o usuario inseriu.
E así, se o usuario malicioso está a ser particularmente intelixente, pode ter ese
volver a algún lugar no printDef función ou nalgún lugar do malloc
función, en calquera lugar arbitrario.
>> Pero aínda máis intelixente é o que se ten o usuario volver á dereita aquí.
E entón comeza a execución de estes como liñas de código.
Entón, nese momento, o usuario pode entrar o que quere para esta rexión.
E ten o control completo sobre o seu programa.
Preguntas sobre iso?
Polo tanto, a seguinte pregunta é completa o reimplementação do foo de tal forma
que non é máis vulnerable.
>> Polo tanto, hai un par de formas podería ter feito isto.
Aínda temos c só sendo de lonxitude 12.
Podería ter cambiado tanto como parte da súa solución.
Tamén engadimos un cheque para facer seguro de bar non era nulo.
Aínda que non ten que para o crédito total.
Entón, nós estamos comprobando o primeiro lonxitude da corda de bar.
De ser maior que 12, entón Non, en realidade, facer a copia.
Así que esta é unha forma de resolve-lo.
>> Outra forma de fixación é, en vez de c tendo só ser de lonxitude 12, telo
ser de lonxitude strlen (bar).
Outra forma de fixar é realmente só retornar.
Entón, se acabase de se librar de todos tanto, se tivese borrado todo
liñas de código, que tería chegado todo o crédito, xa que esta función
en realidade non realizar calquera cousa.
É copiar a liña de comandos argumento nalgún arranxo en
seu cadro de pila local.
E entón a cousa está volvendo.
E o que sexa realizado está desaparecido.
Así, o retorno tamén foi suficiente forma de obtención de crédito total.
>> DAVID J. Malan: Non é así o espírito de a cuestión, pero aceptable pola
especificación, no entanto.
>> ROB BOWDEN: Preguntas sobre nada diso?
O único que, polo menos, precisaba ter compilar o código.
Así, aínda que técnicamente non está vulnerable se o código non
compilar, non acepto iso.
Non hai dúbidas?
Aceptar.
>> DAVID J. Malan: Quere dicir que este título?
>> ROB BOWDEN: Non
>> DAVID J. Malan: Entón, en un regalo, este era ou unha boa nova ou mala noticia.
Este é literalmente o mesmo problema como o primeiro quiz.
E é case o mesmo problema como pset1.
Pero iso foi deliberadamente simplificados para ser unha pirámide máis simple, que pode ser
resolto cun pouco iteración máis simple.
E realmente, o que desplazarse en aquí non era tanto a lóxica,
porque probablemente, por esta época, está máis cómodo do que estaba
nunha semana con loops ou por loops, pero realmente para provocar unha separación que
está un pouco cómodo coa noción de que o PHP non é só sobre o que
programación.
De feito, pode ser usado como unha linguaxe para escribir programas de liña de comandos.
>> E, de feito, é o que nós estabamos intentando de chamar a atención.
Este é un programa para a liña de comandos.
Entón código C aquí, mentres correcta en C, non corrixir a PHP.
Pero o código é realmente o mesmo.
Se comparar as solucións para proba 0 contra o Test 1, podes ver que
é case idéntico, excepto por algúns sinais de dólar e ao
ausencia dun tipo de datos.
En particular, se derme un ollo aquí, verás que iteración, neste
caso, de 1 a 7.
>> Poderiamos ter feito isto 0 índice.
Pero, ás veces, eu creo que é só mental máis fácil pensar sobre as cousas
de 1 a 7.
Se quere un bloque, despois dous bloques, a continuación, tres, entón
punto, punto, punto sete.
Temos xa a ser inicializar a 1 e logo, contando con até i.
E todo aquí é doutro xeito idéntica.
Pero digno de nota son un par de cousas.
Nós dámoslle estas dúas liñas, esta primeira un, goofily nomeado como un shebang
para estrondo afiada.
E iso só especifica o camiño, a cartafol, no que un programa pode ser
descubrín que quere usar para interpretar este ficheiro.
>> E, a continuación, a liña de, despois diso, de por suposto, significa que entre en modo PHP.
E a liña na parte inferior significa saír do modo PHP.
E esta funciona, en xeral, con linguaxes interpretadas.
É unha especie de irritante se escribir un programa nun ficheiro chamado foo.php.
E, a continuación, os usuarios teñen só Lembre, OK, para executar este programa, eu
ten que escribir "espazo php foo.php". Tipo de chat se nada máis.
E tamén revela que o seu programa É escrito en PHP, que non é de todo
que ilumina para o usuario.
>> Así, pode eliminar os ficheiros. PHP totalmente lembrar da clase.
E pode realmente facer. / Foo se vostede chmodded lo, facendo-o
executable.
Entón chmod a + x foo faría iso.
E se tamén engadir a cousa toda aquí.
Pero, en realidade, o problema estaba chegando imprimir algo así.
En HTML, sen C-código certamente, só algunhas PHP.
Entón, Milo despois volveu en 25 problema.
E en 25, recibiu o seguinte código de esqueleto, o cal era un
páxina web moi sinxelo.
E a parte suculenta HTML-wise foi abaixo aquí, onde temos dentro do corpo
unha forma que ten identificación única de insumos no interior do cal foi dúas entradas, unha
cunha idea de nome, un cunha idea de botón.
>> O primeiro foi o tipo de texto, o segundo o tipo de envío.
E, así, deulle, en realidade, máis ingredientes que precisaba, só así
vostedes tiñan opcións coas que para resolver este problema.
Non precisa estrictamente todas estas identificacións.
Pero permite que resolva isto de diferentes xeitos.
E na parte superior, teña en conta que obxectivo foi desencadear
unha fiestra como esta -
Ola, Milo! -
emerxente no navegador usando o super sinxelo, se
, A función de alerta non fea.
E así, en última instancia, é dicir resume-se conceptualmente dalgún xeito, escoitando
submissões de client-side a forma , Non o lado do servidor, dalgunha forma
responder a esta submisión por agarrando o valor que o usuario inseriu
para o campo de nome e, a continuación, amosar-la no corpo dun alerta.
>> Así, unha forma de facelo é con jQuery, que se parece un pouco
sintaticamente desconcertante ao principio.
Podes facelo co código DOM pura - document.getelement por ID.
Pero imos dar un ollo nesta versión.
Eu teño un par de importantes liñas primeiro.
Entón, un, temos esta liña, que é o mesmo que o que se pode ver
en, creo, form2.html de clase a semana 9.
E este é só dicir, executa o código a seguir cando
o documento está listo.
Esta sendo importante só porque Páxinas HTML son lidas de arriba
abaixo, de esquerda a dereita.
>> E, polo tanto, se tentar facer algo no código-se aquí para algúns DOM
elemento, algúns tag HTML, que é baixo aquí, está facendo iso moi pronto,
porque este non ten sequera foi lido na memoria.
Entón, ao dicir isto document.ready liña, estamos dicindo,
aquí está un código, navegador.
Pero non realizar este ata que o todo documento está listo, que é o DOM
árbore existe en memoria.
Este é un pouco máis simple, se sintaticamente un
pouco diferente, onde estou dicindo, Grab o elemento HTML, cuxa única
identificador é insumos.
Iso é o que o hash tag denota o ID único.
E entón eu estou chamando. Enviar.
>> So. Presentar aquí é unha función, se non, coñecido como un método, que é
dentro do obxecto na man esquerda banda, hai que eu non destacar.
Entón, se pensar en entradas como un obxecto na memoria - e de feito é.
É un nó nunha árbore -
. Enviar medios cando este formulario con esa identificación é presentada, executa
o código a continuación.
Eu non me importa o que o nome do función é que estou executando.
Entón, aquí está a usar, como antes, o que se chamada a función lambda ou un
función anónima.
Non é de todo intelectualmente interesante que non ten ningún nome,
o que é bo se está só non vai chamalo dunha vez.
E alí dentro realmente soster a presentación do formulario.
A primeira vez que declarar unha variable chamado valor.
E entón, cal é o efecto desta resaltado parte aquí, agora?
O que isto fai nun alto nivel para min?
>> Audiencia: Queda o valor que o usuario non está en HTML de embaixo.
Ela recibe ese ID e, a continuación, comprobar que o valor do mesmo.
>> DAVID J. Malan: Exactamente.
El agarra o no, cuxo único identificador é o nome.
Comeza o valor nel, o que é, presuntamente, o que o usuario
ingresaran si mesmo.
E entón el almacena que no variable chamada valor.
Como un aparte, tamén se pode ser feito isto un pouco diferente.
Totalmente aceptable, facendo algo valor mentira var queda
document.getElementById.
E é por iso que é un pouco tedioso para non usar jQuery.
"Nome". Valor.
Entón, totalmente aceptable.
Diferentes formas de facelo. jQuery só tende a ser un pouco máis sucinta e
definitivamente máis populares entre os programadores.
>> Agora, eu estou facendo un pouco de cordura comprobar, xa que o problema
declaración nos dixo explicitamente, se o usuario aínda non ingresaran seu
nome, non mostran unha alertas.
Pero pode comprobar que, en só comprobando a cadea baleira para unha
entre comiñas, se hai nada realmente alí.
Pero se non é igual, entre comiñas, Quero chamar alertas.
E a parte interesante aquí é que estamos a usar o operador máis, que
fai o que en JavaScript?
Concatenar.
Entón, é como operador punto de PHP.
A mesma idea, sintaxe un pouco diferente.
E eu estou só creando a cadea que viu na captura de pantalla -
Hola, así e así.
>> E entón o último detalle é o seguinte.
Por que eu return false dentro desta función anónima?
>> Audiencia: Non hai ningún valor.
Poñelas en forma.
El só di que, se o valor non é igual en branco, a continuación, facelo.
Había un baleiro no que a submisión.
>> DAVID J. Malan: Aceptar.
Coidado, porén.
Non hai ninguén aquí.
E ese retorno é falso fóra do, se as condicións.
Pode que a liña resaltada, regresar false, executa, non importa o cando
o formulario é enviado.
O que fai voltar false dentro deste manipulador de eventos, como se chama,
o evento en cuestión sendo submisión?
>> Audiencia: Por só acontece unha vez.
>> DAVID J. Malan: só acontece unha vez.
Non é ben así.
Si?
>> Audiencia: Ela impide que a forma de someténdose o comportamento por defecto,
o que sería a páxina se recargue.
>> DAVID J. Malan: Exactamente.
Entón, eu estou sobrecarregando o prazo presentar aquí, porque eu estou dicindo, é o xeito
sendo sometido.
Pero, como suxire, en realidade non é foi presentado no verdadeiro camiño HTTP.
Premendo en Enviar, por mor da nosa manipulador onSubmit, estamos interceptando
que a submisión do formulario, por así dicir.
Estamos entón a facer o noso cousa con código JavaScript.
Pero eu estou volvendo deliberadamente falsa, porque o que eu non quero que ocorra un
fracción de segundo despois é para toda a forma -Se a ser sometido á web
servidor con pares de valores clave, cambiando o URL para ser algo así como
q = gatos ou calquera outra cousa que fixemos, por exemplo, en clase.
Eu non quero que isto ocorre, por que non hai ningunha escoita servidor para esta
formar submisión.
É puramente en código JavaScript.
E é por iso que eu non tiña sequera un atributo action no meu formulario, por que eu
Non pretendo que isto sempre ir ao servidor.
>> Entón, está a ser sometido.
Pero estamos interceptando que forma submisión e impedindo que o estándar
comportamento, o que é en realidade percorrer todo o camiño para o servidor.
>> Audiencia: Entón mantelo do lado do cliente.
>> DAVID J. Malan: Mantendo do lado do cliente del.
Exactamente.
Logo foi a miña oh MySQL
>> ROB BOWDEN: Aceptar.
Polo tanto, esta primeira pregunta foi, en xeral duro para a xente.
Aínda que os posteriores foi mellor.
Entón tiña que escoller os datos correctos tipo de ambas as columnas.
E ambos teñen algúns cousas sobre eles que
facer a elección difícil.
Entón int non era un válido tipo de número.
A razón de ser dunha conta de 12 díxitos número, un int non é grande abondo para
almacenar totais díxitos.
Así, unha opción válida sería un gran int se ocorrer de saber diso.
Outra opción podería ser un campo de carácter de lonxitude 12.
Así, ou daqueles tería funcionando.
Int non.
>> Agora, o balance, creo que volta a pset7.
Así, especialmente usado para decimal almacenar o valor de accións ou -
>> DAVID J. Malan: Diñeiro.
>> ROB BOWDEN: Diñeiro.
Usan decimal para almacenar a cantidade de diñeiro que o usuario posúe actualmente.
Así, a razón pola que facemos isto é porque, recorda, flota.
Hai de punto flotante de precisión.
Non pode precisamente gardar o diñeiro valores como queiramos aquí.
Entón decimal é capaz de precisión tenda algo, digamos, dúas cifras decimais.
É por iso que o equilibrio, queremos que el ser decimal e non flotan.
>> DAVID J. Malan: E tamén, tamén, aínda que que podería ser intelixente noutro
contextos para pensar, quizais esta é unha oportunidade para un int.
Vou manter o control de cousas en moedas de un centavo.
Porque nós explicitamente mostrou o estándar valor de ser 100.00, que
significa que podería ser só un int.
E outra sutileza tamén co número de foi que non se fixo
para ser unha pegadinha.
Pero lembre que un int en MySQL, como en C, polo menos en
aparello, é de 32 bits.
E aínda que non esperamos que saber exactamente cantos díxitos que
medios, recordo que o maior número podes representar potencialmente
cun número de 32 bits é máis ou menos o que?
>> Cara a un número que sempre di?
2 a 32, que é o que máis ou menos?
Non ten que saber con precisión.
Pero máis ou menos é útil na vida.
É preto de 4 millóns de dólares.
Entón nós dixemos que algunhas veces.
Sei que eu xa dixen iso algunhas veces.
E é máis ou menos 4 millóns.
E iso é unha boa regra de ouro para saber.
Se ten 8 bits, 256 é o número máxico.
Se ten 32 bits, 4 millóns máis ou menos.
Entón, se acabou de escribir 4 millóns, vai ver que é menos díxitos que
12, o que significa que non é claramente expresividade abondo para facer unha
Número de conta de 12 díxitos.
>> ROB BOWDEN: Aceptar.
Entón, os outros correron mellor.
Entón supoño que a base impón unha mensual $ 20
taxa de mantemento en todas as contas.
Con que pesquisa podería banco deducir $ 20 a partir de cada conta, aínda que
que resulta nalgúns saldos negativos?
Entón, basicamente, hai catro principais tipos de consultas -
introducir, seleccionar, actualizar e eliminar.
Entón, o que pensamos que somos vai utilizar aquí?
Actualiza.
>> Entón, imos dar un ollo.
Entón, aquí estamos a actualizar.
O cadro que estamos a actualizar as contas?
Entón actualizar contas.
E entón a sintaxe di, o que en contas estamos a actualizar?
Ben, estamos establecendo equilibrio igual ao valor actual de equilibrio menos 20.
Entón, isto vai actualizar todas as liñas de todo, subtraindo
20 $ a partir do equilibrio.
>> DAVID J. Malan: Un erro común aquí, aínda que, por veces, perdoou-o,
era, en realidade, ten o código PHP aquí chamando a función de consulta ou poñer
comiñas en torno a todo o que Non precisa estar alí.
>> ROB BOWDEN: Lembre que MySQL é unha lingua separada do PHP.
Temos que ser escrito MySQL en PHP.
E PHP é, entón, envialo ao servidor MySQL
Pero non precisa de PHP, a fin de comunicarse con un servidor MySQL
>> DAVID J. Malan: Exactamente.
Polo tanto, non variables con cifrões debe ser, neste contexto.
El só pode facer toda a matemática dentro da propia base de datos.
>> ROB BOWDEN: Aceptar.
Entón a próxima.
Este é o próximo?
É.
Así, co que podería pesquisa da base recuperar os números de contas da súa
clientes máis ricos, aqueles con contrapesos maiores que 1000?
Así que un dos catro tipos principais imos querer aquí?
Seleccione.
Por iso, queremos seleccionar.
O que queremos para seleccionar?
Cal columna que queremos seleccionar?
Imos especificamente quere para seleccionar un número.
Pero se dixo que estrela, nós Tamén aceptou iso.
>> Entón, seleccione o número a partir do que mesa?
Contas.
E entón a condición que queremos?
Onde equilibrio maior que 1.000.
Tamén estou de acordo máis ou igual.
Último.
Con que pesquisa podería banco seguinte, ou sexa, eliminar todas as contas que
ten un saldo de US $ 0?
Entón, cal dos catro somos nós Vai querer usar?
Eliminar.
Así, a sintaxe para iso?
Eliminar o cadro?
Contas.
E, a continuación, a condición na cal que quere eliminar -
onde o equilibrio é igual a cero.
Entón, eliminar todas as liñas de contas onde o saldo é cero.
Preguntas sobre calquera destes?
Queres cola?
>> DAVID J. Malan: guía Cola.
Entón, en un regalo, que lle deu un pouco estrutura familiar que explotou unha
bits en clase xunto de estruturas, que foi unha datos
estrutura relacionada en espírito.
A diferenza, aínda que cunha cola é que tivemos que lembrar de algunha maneira que
estaba diante da cola, en gran parte para que puidésemos facer máis
uso eficiente da memoria, polo menos se estivésemos usando un array.
>> Porque recall, se temos unha matriz, se, por exemplo, esta é a cabeza
cola, se eu entrar na cola aquí, e entón alguén entra na cola
detrás de min, detrás de min, detrás de min, e unha persoa sae de liña,
podería, como xa vimos algúns dos nosos humano voluntarios en clase, teñen todos
cambiar esta forma.
Pero, en xeral, despois de todo facer algo non é o mellor uso do tempo
nun programa, porque iso significa que o seu algoritmo está a ser executado en
tempo de execución asintótica?
É lineal.
>> E eu sinto que este é o tipo de estúpido.
Se a seguinte persoa da cola é o seguinte persoa que debería ir ao
tenda, eles non teñen para mover en conxunto.
Só deixe que a persoa pode arranquei cando chegar a hora, por exemplo.
Así, podemos aforrar un pouco de tempo alí.
E así, para facelo, con todo, que os medios que o xefe de fila ou a
cabeza da cola vai progresivamente moverse máis e máis
na matriz e, finalmente, pode realmente participa en torno de si estamos usando un
matriz para almacenar a xente nesta cola.
Entón case pode pensar no matriz como unha datos circular
estrutura nese sentido.
>> Entón, dalgunha forma ten que manter o control do tamaño del ou realmente o fin de todo
e logo, onde o inicio do que é.
Así, propoñemos que declarar un tal cola, a chamada
el q, só unha letra.
Logo propoñemos que a fronte é iniciar a cero, e que o tamaño
ser inicializado a cero.
>> Entón, agora, non hai nada dentro desa fila.
E pedimos-lle para completar a implementación de poñela na fila de abaixo en
tal xeito que a función engade n á a fin de q e, a continuación, devolve verdadeiro.
Pero se q é completa ou negativa, o función debe voltar false vez.
E deulle un par de suposicións.
Pero eles non son realmente funcionais relevante, hai só que bool,
porque, tecnicamente, bool non existen en C, a non ser que inclúa un
determinado ficheiro de cabeceira.
Así que acaba de asegurarse de que non foron este é un truco
cuestión tipo de cousas.
>> Entón, poñela na fila, propuxemos na mostra As solucións para aplicación como segue.
Un, nós primeiro comprobar a facilidade, os froitos baixo colgado.
Se a cola está chea ou o número que estás a introducir é menor
que cero, o que dixemos no especificación do problema debe
non ser permitido, porque nós só queremos valores non negativos, entón ten que
só return false inmediatamente.
Así, algúns relativamente fácil comprobación de erros.
Que quere engadir que real número, tiña que facer un pouco de
pensando aquí.
E é aí que é un pouco aburrido mental, porque ten que
descubrir como xestionar a envolvente.
>> Pero o xerme da idea aquí é de interese para nós é que a envolvente
moitas veces implica aritmética modular e o operador mod, o lado por cento,
onde pode ir dun valor maior de volta a cero e, a continuación, un e dous e
tres e, a continuación, de volta ao redor de cero, un e dous e tres, e así por diante
unha e outra vez.
Así, o xeito propoñemos facelo é que queremos índice para a
array chamado números onde nosos enteiros mentir.
Pero para chegar alí, primeiro quero facer sexa cal sexa o tamaño da cola é mais
a continuación, engade a iso calquera que sexa a cabeza da lista é.
E o efecto que é poñer-nos en a posición correcta na cola e
Non supoña que a primeira persoa en liña é, en principio, que el ou
ela absolutamente podería ser se nós Tamén foron cambiando todo.
Pero estamos só a creación de traballo para nós mesmos, se nós tomamos
ese camiño particular.
>> Así, podemos mantelo relativamente simple.
Temos que lembrar que nós só engadido un int á cola.
E entón nós só volver true.
Mentres tanto, en dequeue, pedimos que faga o seguinte.
Implementar lo de tal forma que eliminada da cola, ou sexa, elimina e volve,
int diante da cola.
Para eliminar o int, simplemente esquece-lo.
Non precisa substituír a súa parte.
Entón, aínda é realmente alí.
Así como os datos de un disco duro, estamos só ignorando o feito de
que agora é alí.
E si q está baleira, hai que en vez voltar negativo 1.
Entón, este se sente arbitraria.
Por que voltar negativo 1 en vez de teito?
É.
>> Audiencia: Q está almacenando valores positivos.
Dende que só almacenar valores positivos no q, negativo é un erro.
>> DAVID J. Malan: OK, é certo.
Entón por que nós só estamos almacenando positivo valores ou cero, así que non hai problema en
voltar un valor negativo como unha sentinela valor, un símbolo especial.
Pero está reescribir a historia alí, porque a razón estamos só
retornando valores non negativos é porque queremos
ten un valor de sentinela.
Entón, en concreto, xa non basta return false en caso de erro?
É.
>> Audiencia: Vostede fallou para volver un enteiro.
>> DAVID J. Malan: Exactamente.
E é aí que queda C moi constrangedor.
Se está dicindo que está indo para volver un int, ten
para volver un int.
Non pode comezar a fantasía e comezar a devolver un booleano ou un float ou un
corda ou algo parecido.
Agora, con todo, JavaScript e PHP e algunhas outras linguas pode, de feito,
retornar diferente tipo de valores.
E iso pode ser realmente útil, onde podería voltar Ints positivas, ceros,
Ints negativos ou falso ou nulo mesmo para significar erro.
Pero non hai que versatilidade en C.
>> Así, con dequeue, o que propoñer a facer é -
>> ROB BOWDEN: Pode voltar false.
É só que falsa é de hash establecer teito a cero.
Entón, se voltar false, está retornando cero.
E cero é algo válido na nosa fila, mentres que un negativo non é se
falsa pasou a ser negativo 1.
Pero non debe mesmo que saber diso.
>> DAVID J. Malan: Isto é por iso que eu non dixen iso.
>> ROB BOWDEN: Pero non era verdade que non pode voltar false.
>> DAVID J. Malan: Por suposto.
Entón dequeue, teña en conta que aceptamos invalidar como o seu argumento.
E iso é porque non somos pasar nada dentro
Nós só queremos eliminar o elemento na parte da fronte da cola.
Entón, como podemos facer sobre iso?
Ben, primeiro, imos facelo verificación de sanidade rápida.
O tamaño da cola é de 0, non hai ningún traballo a ser feito.
Retorno negativo 1.
Feito.
Entón, iso é algunhas liñas do meu programa.
Así, só catro liñas permanecen.
>> Entón, aquí eu decidir diminuír o tamaño.
E diminuíndo o tamaño efectivo significa que eu estou esquecendo
algo está aí.
Pero tamén teño que actualizar onde adiante son os números.
Entón, para facelo, eu teño facer dúas cousas.
Eu primeiro que lembrar que o número está diante da fila,
porque eu teño volver aquela cousa.
Entón eu non quero esquecer accidentalmente sobre el e, a continuación, substitúe-lo.
Eu só vou lembrar dun int.
>> E agora, quero actualizar q.front ser q.front 1.
Polo tanto, se esta foi a primeira persoa en liña, agora, quero facer máis 1 para
apuntar á seguinte persoa na cola.
Pero eu teño que tratar con isto envolvente.
E se a capacidade é unha constante global, que vai permitir-me para asegurarse de
como eu apuntar á última persoa en liña, a operación do módulo pode traer
me de volta a cero no cabeza da cola.
E que manipula a envolvente aquí.
E entón eu proceder para voltar n.
>> Agora, a rigor, non o fixen ten que declarar n.
Eu non teño que agarrá-lo e almacena-lo temporalmente, xa que o valor é
aínda está alí.
Entón, eu podería só facer a aritmética dereita para volver o ex xefe
da cola.
Pero eu sentín que este era máis clara para realmente incorporarse o int, poñelas
en n, e despois volver que por unha cuestión de claridade, mais
non estrictamente necesario.
Psst.
Son todos pronunciável na miña cabeza.
>> ROB BOWDEN: Entón, primeira pregunta é o problema de árbore binaria.
Entón, primeira pregunta é, somos dado a eses números.
E queremos inserir-los de algunha maneira en destes nós a fin de que el é un
válido árbore de busca binaria.
Entón a única cousa a lembrar sobre árbores de busca binária é que el non é
só que a cousa á esquerda é menor e a cousa a
o dereito é maior.
Ten que ser que toda a árbore para esquerda é menor, e toda a árbore
á dereita é maior.
>> Entón, se eu poñer 34 aquí na parte superior, e despois Engada 20 aquí, entón iso é válido para que
agora, porque o 34 por aquí.
20 vai á esquerda.
Entón, iso é menos.
Pero eu non podo entón poñer 59 aquí, porque aínda 59 está á dereita, de 20,
que aínda está á esquerda do 34.
Así, con esta restrición en mente, o xeito máis doado de solucionar este probablemente
problema é só unha especie destes números -
entón 20, 34, 36, 52, 59, 106.
E, a continuación, introduza os de esquerda a dereita.
>> Entón 20 vai aquí.
34 vai aquí.
36 vai aquí.
52, 59, 106.
E tamén pode descubrir con algúns conectar e entender,
Oh, espera, eu non teño números suficientes para cubrir esta en máis aquí.
Entón eu teño que meu reshift ruta nota será.
Pero teña en conta que en tres finais, se le de esquerda a dereita, é o
orde crecente.
>> Entón, agora, queremos declarar que a struct será ao
nós nesta árbore.
Entón o que necesitamos nunha árbore binaria?
Polo tanto, temos un valor de tipo int, de xeito algún valor int.
Eu non sei o que chamamos O na solución -
int n.
Necesitamos un punteiro para o fillo esquerdo e un punteiro para o fillo dereito.
Entón el se ve así.
E vai realmente ollar antes cando é que o dobremente vinculada
lista cousas, entón aviso -
Vou ter que percorrer todo o camiño de volta para o problema 11.
>> Entón, teña en conta que parece idéntica a esta, agás que só terá lugar a chamar estes
nomes diferentes.
Aínda temos un número enteiro valor e dous punteiros.
É só que, no canto de tratar a punteiros como apuntar á seguinte cousa
e do anterior, estamos tratando os punteiros para ligar a un fillo esquerdo
e fillo dereito.
Aceptar.
Entón, este é o noso nodo struct.
E agora, a única función que necesitamos aplicar para iso é transversal, que
queremos pasar por riba da árbore, a impresión os valores da árbore de orde.
>> Entón, mirando aquí, queremos imprimir a 20, 34, 36, 52, 59 e 106.
Como é que imos conseguir isto?
Polo tanto, é moi similar.
Se viu o exame pasado o problema que quería imprimir
toda a árbore co comas entre todo, era, en realidade, incluso
máis fácil do que iso.
Entón aquí está a solución.
Isto era significativamente máis fácil se fixo iso de forma recursiva.
Non sei se alguén intentou para facelo de forma iterativa.
>> Pero, primeiro, temos o noso caso base.
E si a raíz é nulo?
Entón, nós só estamos indo a retornar.
Non queremos para imprimir calquera cousa.
Else imos atravesar recursivamente abaixo.
Imprimir toda a subárvore esquerda.
Entón imprimir todo menos que o meu valor actual.
E entón eu vou imprimir.
E entón eu estou indo para a miña recursão toda subárvore dereita, entón todo
maior que o meu valor.
E iso vai imprimir todo en orde.
Preguntas sobre como isto realmente realiza isto?
>> Audiencia: Eu teño unha pregunta no [inaudível].
>> ROB BOWDEN: Polo tanto, unha forma de achegarse calquera problema recursivo é só pensar
sobre el gusta de ti tes que pensar sobre todos os casos de canto.
Por iso, considero que queremos imprimir esta árbore enteira.
Entón, todos nós estamos indo focalizar en é este nodo específico -
36.
As chamadas recursivas, nós fingimos quen só traballar.
Entón, aquí, esta chamada recursiva para transversal, que, sen sequera pensar
sobre iso, só atravesando a esquerda tres, imaxina que xa imprime 20
e 34 para nós.
E entón, cando finalmente, de forma recursiva chamar travesía sobre o
dereita, que pode imprimir correctamente 52, 59, e 106 para nós.
>> Así, dado que esta pode imprimir 20, 34, e o outro pode imprimir 52, 59, 108,
todo o que necesitamos para poder facer é imprimir nós mesmos, no medio diso.
Entón imprimir todo antes de nós.
Imprimir a nós mesmos, co fin de impresión no actual 36, printf regular, e, a continuación,
imprimir todo detrás de nós.
>> DAVID J. Malan: Este é o lugar onde a recursión queda moi bonito.
Este salto incrible de fe, onde fai un pouquiño de traballo.
E entón deixar a alguén máis facer o resto.
E que outra persoa é, ironicamente, ti.
Entón, por graves brownie puntos, se se despraza cara arriba sobre as cuestións -
>> ROB BOWDEN: Nas preguntas?
>> DAVID J. Malan: E un pouco para abaixo para os números, alguén sabe onde
estas cifras veñen?
>> ROB BOWDEN: Eu teño literalmente ningunha idea.
>> DAVID J. Malan: Aparecen durante todo o exame.
>> Audiencia: Son eles os mesmos números?
>> DAVID J. Malan: Estes números.
Un pouco de ovo de Pascua.
Polo tanto, para aqueles de vostedes asistir en liña en casa, se nos pode dicir por correo electrónico a
heads@CS50.net que o significado estas cifras son repetidos seis
todo Proba 1, imos lava-lo con incrible atención na final
charla e unha bola de estrés.
Niza, sutil.
>> ROB Bowden: Calquera últimas preguntas sobre calquera cousa sobre a proba?