DAVID Malan: Todo ben. Benvido de volta ao CS50. Este é o inicio da semana 8. E lembrar que problema set rematou 5 cun pouco de un reto. Así, supoñendo que recuperou todo o seu Compañeiros de ensino e fotografías da CA no ficheiro card.raw, vostede é elegível agora atopar todas esas persoas, e un afortunado gañador vai a pé a casa cun destas cousas, o movemento salto dispositivo que pode usar para a final proxectos, por exemplo. 

Este, cada ano, leva a un pouco de bizarrice. E así que eu penso que eu ía facer é compartir contigo algunhas das notas que teñen ir para atrás e cara adiante sobre a lista de funcionarios da tarde. Por exemplo, onte á noite, citas unquote, a partir dun dos funcionarios membros ", eu só tiña unha batida estudante na miña porta para sacar unha foto comigo. Stalkers, eu lle digo. "Empezou moi descriptivo e despois nos mudamos para, unha hora máis tarde, "Eu tiven un estudante esperando por min despois da sección e tiña todos os nosos nomes e fotos nalgunhas follas de papel. "Todo ben. Así organizado, pero non todo o que asustado aínda. 

Entón, "Eu estaba fóra da cidade neste fin de semana, e cando volvín, había un en meu cuarto. "[risas] DAVID Malan: Next cita dun equipo membro ", dixo un alumno chegou á miña casa en Somerville ás 4 da mañá, esta mañá. "Next persoal, "Eu cheguei ao meu hotel en San Francisco e un alumno estaba esperando por me no hall de entrada con tres DSLRs. " Tipo de cámara. "Eu non estou nin no equipo neste semestre, pero un estudante invadiu a miña casa esta mañá e rexistrou a cousa toda con vidro de Google. "E entón, finalmente, "Polo menos 12 persoas foron avidamente agardando para min cando eu saín do meu limo, e entón eu espertei. "Todo ben. Así, entre as fotografías, como pode lembrar, son este home aquí, que pode saber como Milo bananas, que vive con Lauren Carballo, a nosa cabeza ensino Fellow. Milo, Milo, ven acá neno. Milo. Milo. Lembre, está a usar Google de vidro, de xeito imos amosar todo isto despois. Polo tanto, esta é Milo se desexa tirar unha foto con el despois. Se desexa ollar para fóra para o público alí. Aceptar. Isto é bo filmación. Ben, Milo bananas. Oh, non fagas iso. 

[Risas] 

Aceptar. Así, unha palabra, a continuación, sobre o que está por vir, porque cando comezamos a transición, esta semana en concreto, a partir de C, nunha ámbito de liña de comandos para PHP e Javascript e SQL e HTML e CSS en un ambiente baseado na web, estaremos equipando o con toda máis coñecemento para potenciais proxectos finais. Para iso, o curso ten unha tradición de realización de seminarios que son sobre temas tanxenciais ao curso. Moi relacionado coa programación e desenvolvemento de aplicacións e así por diante, pero non necesariamente por explotado propio plan de estudos da carreira. 

Entón, se podería estar interesado en un ou máis de seminarios deste ano, rexistrar en cs50.net/seminar. Existen seminarios anciás en cs50.net/seminars. E o conxunto, ata agora, para este ano son sorprendentes aplicacións web con Ruby on Coches, que é unha alternativa linguaxe para PHP. Lingüística computacional. Introdución á iOS, que é o plataforma que se usa para o iPhone e desenvolvemento iPad. JavaScript para Web Apps, imos cubrir iso, pero neste seminario, vai en máis detalle. 

Leap Movemento, entón imos realmente ter algún dos nosos amigos da Leap Movemento, da propia empresa, unirse a nós. Mañá, en realidade, para facilitar un hands-on seminario, se do seu interese. Meteor.js, unha técnica alternativa para mediante JavaScript e non nun navegador, mais nun servidor. Node.js., que é moi nesa vea ben. Deseño elegante Android. Android ser unha alternativa moi popular para iOS e Windows Phone e outras plataformas móbiles. Correo web Active defensiva Seguridade. 

Entón, en realidade, se quere involucrarse en iso, déixeme anota isto. Estamos moi felices en dicir que nosos amigos en Salto De movemento, que é unha inicialización - este dispositivo realmente acabou fóra hai uns meses - graciosamente doaron 30 dispositivos para a clase de como moitos alumnos, se quere pedir o hardware cara ao final do semestre, e usalo para un proxecto real final. Eles soportan varios idiomas. Ningún deles C, ningún deles PHP, así entender un ou máis destes seminarios pode revelar-se de interese. E todos eles van ser filmado en caso en que non é capaz para comparecer en persoa. A programación será anunciada vía enviar correo-e como se solidificar cuartos. 

E, por último, se vai a projects.cs.50.net, este é un sitio temos cada ano que invitados persoas da comunidade, profesores, departamentos, funcionarios e dous nun lado de fóra de CS50 para propoñer ideas para proxectos. Cousas de interese para grupos de estudantes. Cousas de interese para os departamentos. Entón non virar alí, se está loitando coa incerteza en canto ao que se quere afrontar. 

Entón última vez que introduciu unha indiscutibelmente estrutura de datos máis complexa do que tiñamos ver nas últimas semanas. Estabamos a usar matrices moi feliz como un útil se estrutura de datos simplista. Entón, nós introducimos estes, que por suposto están ligados listas. E o que foi unha das motivacións para introducindo esta estrutura de datos? Si? ¿Que é iso? 

Audiencia: tamaño dinámico. 

DAVID Malan: tamaño dinámico. Así, mentres en orde, ten que coñecer con antelación o seu tamaño cando vostede reservar-lo. Na lista ligada, non ten que saber iso. Pode só malloc, ou, máis xeralmente, asignar un adicional no, por así dicir, en calquera momento pretende introducir máis datos. O nodo ten ningún significado pre-determinado. É só un termo xenérico que describe algún tipo de recipiente que estamos usar na nosa estrutura de datos para almacenar algún elemento de interese, que neste caso ocorrer de ser enteiros. 

Pero sempre hai un intercambio. Entón, temos tamaños dinámica dos datos estrutura, pero o prezo que imos pagar? Cal é a desvantaxe de listas ligadas? Si? 

Audiencia: Require máis memoria. 

DAVID Malan: Esixe máis memoria, como exactamente? 

Audiencia: [inaudível]. 

DAVID Malan: Exactamente. Entón, agora temos punteiros ocupando memoria adicional que anteriormente non precisa, xa que a vantaxe dunha matriz, por suposto, é que todo é contiguo, de volta de volta cara atrás, o que dálle acceso aleatorio. Porque só usando corchete notación, ou máis técnicamente punteiro aritmética, adición moi sinxelo, pode acceder a calquera elementos en tempo constante. E, de feito, este é o tipo de insinuando outro prezo que estamos pagando cun lista ligada. 

Que pasa co tempo de execución algo así como Search, se eu queira atopar algún valor e no interior dunha lista ligada? O que o meu tempo de execución se fixo? Big O de n. De ser clasificada para? E se a estrutura de datos é clasificado? Eu podo facer mellor que un gran O de n para a investigación? Non, porque no peor dos casos pode moi ben ser clasificado, pero o número está a buscar pode ser grande. Pode ser o número 100, o cal pode ocorrer de ser todo o camiño ao final. E por que só se pode acceder a un linked lista nesta implementación por camiño de seu primeiro nodo, está Aínda medio fóra de sorte. Ten que atravesar a cousa toda do primeiro ao último, a fin de atopar que gran valor como 100. Ou para determinar se é nin mesmo alí. 

Polo tanto, non podemos facer o algoritmo nun conxunto de datos estrutura que se parece con isto? Non podemos facer busca binária, porque busca binaria necesario que tiñamos de acceso aleatorio. Poderíamos simplemente ir de local para lugar, sen ter que seguir estas migas de pan en forma todas estas indicacións. 

Agora, como é que imos aplicar iso? Ben, se somos a pantalla aquí, se podemos reimplementar rapidamente estes datos estrutura - miña carta non é todo o que gran aquí, pero imos tratar. Typedef struct Entón, eo que eu fixen quero chamar esa cousa aquí enriba? Node. Entón, eu vou ser un bo comezo. E agora, o que ten que estar dentro a estrutura de datos para que, illadamente lista ligada? Cantos campos? 

Así, dous. Un deles é moi sinxelo. Entón, int n. E poderiamos chamar n todo o que queremos, pero debe ser un int se estamos implementación dunha lista encadeada para ints. E agora que é o que a segunda campo ten que ser? Struct node *. Entón, se eu fai struct node *, e entón eu pode chamar iso tamén o que eu queira, pero só para quedar claro que vou chamar lo xunto, como temos benvida a facer. E entón eu vou pechar meus chaves. 

E agora, como a última vez, Engada nó aquí. Pero se eu estou declarando que é como un no, por que eu me incomodo de ser tan detallado aquí na declaración struct * Nodo seguinte, en oposición só nodo * next? Si? 

Audiencia: [inaudível]. 

DAVID Malan: Exactamente. Exactamente. Por C realmente leva literalmente e ve só a definición de nodo ata aquí, non pode consultalo-lo aquí. Entón temos este tipo de preferencia declaración aquí, que é recoñecidamente máis detallado. Struct nodo, o que significa agora podemos acceder a ela no interior da estrutura de datos. 

E, como unha banda, porque iso é tornándose un pouco máis subjetiva, agora, a estrela tecnicamente pode ir aquí, pode ir aquí, pode incluso ir no medio. Adoptado, na guía de estilo para o curso, o acordo de poñer a estrela ao lado dos datos tipo, que, neste caso, sería no struct. Pero entender en unha morea de libros e referencias en liña, pode de feito vela do outro lado. Pero só entender que ambos realmente traballar e ten que simplemente ser consistente. 

Todo ben. Entón esa foi a nosa declaración de nó struct. Pero, entón, comezan a facer máis cousas sofisticadas. Por exemplo, decidimos introducir algo así como unha táboa hash. Entón, aquí está unha táboa hash de tamaño n, indexados a partir de 0 na esquina superior esquerda para n menos un na parte inferior esquerda. Este podería ser un hash mesa para nada. Pero que tipo de cousas que falamos sobre o uso dunha táboa hash para? Gardar o que? 

Nomes. Poderiamos facer nomes como fixemos a última vez. E realmente, pode almacenar calquera cousa. E veremos iso de novo en PHP e JavaScript. Unha táboa é un bo tipo de suízo Canivete que permite que almacene practicamente todo o que queiras dentro que asociando chaves con valores. Chaves con valores. 

Agora, neste caso simple, a nosa claves son só números. Estamos implementando un hash táboa como unha matriz. E para que as teclas son 0, 1, 2, e así por diante. E así nós, como seres humanos, decidiu última semana que sabe que, se estamos indo para almacenar nomes, imos arbitrariamente, pero moi razoable, supoñer que Alice, un A nome só vai ser indexado en 0. E Bob, un nome de B, será indexado en 1, e así por diante. Entón, tivemos un mapeamento entre entradas, que son cordas, eo hash lugares, que son números. 

Así que o proceso é xeralmente coñecido como unha función de hash, e realmente pode implementar lo en código. Se eu quixese aplicar unha función hash que fai exactamente o que nos acabamos de describir a última vez, eu podería declarar unha función que recibe como entrada, por exemplo - e imos facelo neste pantalla aquí. Se eu quixese aplicar un hash función, eu podería dicir algo así. 

Vai voltar un int. Será chamado de hash, e é vai aceptar como argumento un cadea, ou podemos ser máis axeitado agora, e dicir char *, imos chamalo s. E entón, esta función ten que facer, en última instancia, é voltar un int. Agora, como fai iso pode non ser tan clara. Vou aplicar iso sen forma de comprobación de erros no momento. Eu só vou dicir cegamente, o regreso o que está á s soporte 0, menos, imos dicir, o capital Un punto e coma. 

Totalmente roto. Non é perfecto, porque un, o que se s é nulo? Cousas malas van ocorrer. Dous, e se a primeira letra neste nome non é unha letra maiúscula? Iso non vai virar saír ben tamén. Pode ser unha letra minúscula ou non unha carta a todos. Entón, totalmente espazo para melloras aquí, pero esa é a idea básica. 

Que describiu a semana pasada como verbalmente só un proceso de cartografía de Alicia 0 e Bob 1 pode ser expresada certamente máis formulaically como C funciona aquí. Chamado novo hash recibe unha cadea como entrada e de algunha maneira fai algo co que a entrada para producir unha saída. Non moi diferente da nosa descrición da caixa negra que fixemos moito. Non sei como iso se pode traballar debaixo do capó. 

Polo conxunto de problemas 6, un dos retos é para vostede decide o que será a súa función hash ser? O que vai estar dentro do que o negro caixa e, presuntamente, será un pouco máis interesante que iso, e definitivamente máis propenso a erros comprobando que este particular implementación. 

Pero poden xurdir problemas, non? Se temos unha estrutura de datos, tal como esta un, que é un dos problemas pode realizar ao longo do tempo en que inserir máis e máis nomes no táboa hash? Comeza colisións, non? E se ten Alicia e Aaron, dúas persoas cuxos nomes pasou comezar cun? Isto levanta a cuestión, onde poñer o segundo como un nome? 

Ben, pode, inxenuamente, simplemente poñelas onde Bob pertence, pero, a continuación, Bob é tipo de ferrado se tentar introduce o teu nome xunto e non hai espazo para el. Entón pode pór Bob onde Charlie é, e pode imaxinar iso moi rápido devolvendo nun pouco de confusión. Algo lineal, ao final, onde Só ten que buscar a cousa toda buscando Alicia ou Bob ou Aaron ou Charlie. 

Entón, en vez diso, propuxo, no canto de só linearmente enquisa para espazos abertos e estatelando os nomes alí, nos propuxo unha visión máis extravagante. Unha táboa implementada aínda cun variedade de índices, pero o tipo de datos estes índices eran agora punteiros. Punteiros para que? Punteiros para listas ligadas. 

Porque lembran que unha lista ligada é en realidade, só un punteiro a un nodo, e o nodo ten un campo seguinte, e que o nodo ten un campo seguinte, e así por diante. Entón, agora pode pensar desa matriz en o lado esquerdo dunha táboa de hash levando a unha lista ligada. A vantaxe é que se incorporarse un colisión entre Alicia e Aaron, O que fai o segundo tal persoa? Acaba de conectar-lle para o extremo, ou mesmo o inicio desta lista ligada. 

E de feito, imos só mediante pasta que por só un segundo. Onde faría máis sentido? Se eu introducir Alicia e ela acaba a primeira posición, entón eu intento insira o nome de Aaron, e non hai obviamente unha colisión, debo poñer el no inicio da lista ligada? Isto é polo que a primeira posición, ou ao final? 

Audiencia: [inaudível]. 

DAVID Malan: Aceptar. Oín comezando. Por que no inicio? 

Audiencia: [inaudível]. 

DAVID Malan: Aceptar. É alfabética, de xeito que é bo. Esta é unha boa propiedade. El me vai aforrar tempo potencialmente. Non me vai deixar facer busca binaria, pero eu pode polo menos ser capaz de saír dun loop, se eu entender, ben, eu son moi pasado eran Aaron estaría nesta clasificadas lista encadeada. Non teño que perder o meu tempo buscando todo o camiño ata o final. Entón, iso é razoable. Por que máis pode querer inserir nome colidindo no inicio da lista? ¿Que é iso? 

Audiencia: [inaudível]. 

DAVID Malan: Pode levar moito tempo a chegar ao final da lista. E, de feito, máis e máis. Canto máis nomes que inserir Comece unha, máis que cadea se ve. Canto máis tempo que ligaba lista se ve. Entón é realmente só perdendo o seu tempo. Quizais sexa mellor manter tempo de inserción constante, gran O de 1, por sempre poñendo o nome de chocar en o inicio da lista encadeada, e non se preocupe tanto sobre a clasificación. 

Cal é a mellor resposta? Non está claro. É o tipo de depende do que o a distribución é, cal é o defecto é dos nomes que está introducindo. Non é necesariamente unha resposta obvia. Pero aquí, unha vez máis, é unha oportunidade de deseño. 

Entón, a continuación, mirou para esa cousa, que en realidade é a outra gran oportunidade ao p-conxunto 6. E entender, se non ten xa, Zamyla mergulla ambos, hash mesas e trata, de forma máis detallada. E o paso a paso de vídeo incorporado xuntos p-spec. Este foi un trie - T-R-I-E. E o que era interesante isto era que o tempo de execución de buscar un nome, como Maxwell última vez, era grande o de que? ¿Que é iso? 

Audiencia: O número de letras. 

DAVID Malan: Número letras. Oín dúas cousas. Número de letras e de tempo constante. Entón imos coa primeira. O número de letras. Ben, esta estrutura de datos, aviso, é como unha árbore, unha árbore de familia, cada un dos nós cuxas son feitas de matrices. E estas matrices son punteiros para outros tales nós, ou outras, tales matrices na árbore. 

Entón, se nós queriamos, entón, determinar Maxwell se está aquí, eu podería ir para a primeira matriz, na parte superior de a árbore, o chamado raíz, arriba o trie, e segue o punteiro m, a continuación, a un punteiro, entón x, S, E, L, L. E entón cando vexo algún símbolo especial, denotado aquí como un triángulo. No código verás que nos propoñemos que implementado como un bool, só dicindo si ou non, a palabra para aquí. 

Ben, xa que fun á M-A-X-W-E-L-L, Parece que sete, quizais oito se somos un pasado, oito pasos para atopar Maxwell. Ou imos chamalo K. Pero lembre-se pasado banda, argumentou que, se hai realista lonxitude máxima nunha palabra, como algúns personaxes de 40 e tantos, un lonxitude máxima implica un valor constante. Entón, en realidade, si, é tecnicamente gran O de 8 ou 7, ou realmente grande O de K. Pero se hai un límite finito no que K pode ser, é unha constante. E por iso é grande de 1 a ao final do día. 

Non no mundo real. Non cando realmente comezar a asistir o reloxo de carreira do seu programa. É absolutamente vai ser un pouco máis lento que verdadeiramente constante co tempo un chanzo. Vai ser sete ou oito etapas, senón que é moi, moito mellor que un algoritmo como o gran de n que depende do tamaño do que está no estrutura de datos. 

Observe a cabeza aquí é que podemos introducir máis dun millón de nomes para este estrutura de datos, pero cantos máis pasos é el que vai levarnos a atopar Maxwell, neste caso? Ningún. El é afectado. E ata agora, eu non creo que nós vimos un exemplo dunha estrutura de datos ou un algoritmo que foi completamente afectado por factores externos comportamentos coma este. Pero iso non pode ser incrible. Esta non pode ser a única solución ao p-conxunto 

E non o é. Esta non é, necesariamente, os datos estrutura debe gravitar para, porque, como táboas de hash, tradeoff. Cal é o prezo que se paga aquí? Memoria. Quero dicir, isto é unha atroz cantidade de memoria. E non podes velo aquí, porque o autor da imaxe obviamente truncado as matrices, e nós non estamos a ver moitas A e B e C eo Q e E e Z do nesas matrices. Pero eles están alí. 

Cada un destes nós é unha matriz enteira de preto de 26 ou máis bytes, cada un dos que representa unha letra. 27 no noso caso, para que poidamos apoiar apóstrofos no conxunto de problemas. Polo tanto, esta estrutura de datos é, en realidade, realmente densa e ampla. E iso só pode acabar retardando as cousas, ou polo menos lle custa unha moito máis espazo. Pero, de novo, podemos extraer comparacións aquí. 

Lembre-se de un tempo, nós conseguimos moito tempo de carreira máis emocionante na clasificación cando usamos merge sort, pero o prezo pagamos para acadar n log n para fusión tipo esixe que gastamos máis que recurso? Máis espazo. Necesitabamos dunha matriz secundaria a copiar a xente, así como fixemos aquí no escenario. Entón, de novo, hai claros gañadores, pero só proxecto subxectiva decisións a tomar. 

Todo ben. Entón, que tal isto? Calquera persoa recoñecer que D-Hall? Aceptar. Así, tres de nós. Mather House. Polo tanto, esta é para unha cea de Mather. ¿Podería supoñer que todos os comedores teñen pila de bandexas coma este. E iso é realmente representativo de algo que xa obviamente, xa visto. Chamamos-lle, literalmente, unha pila. E a pila, en termos da súa memoria do ordenador, é onde os datos van mentres que as funcións están a ser chamados. 

Por exemplo, que tipo de cousas na pila respecto ao esquema de memoria que discutir nas últimas semanas? ¿Que é iso? 

Audiencia: Chamadas a funcións. 

DAVID Malan: Eu sinto moito. 

Audiencia: Chamadas a funcións. 

DAVID Malan: Chamadas para funcións, pero En concreto, o que está dentro de cada un estes cadros? Que tipo de cousas? Si Así, as variables locais. Sempre que necesitabamos dalgún almacenamento local, como un argumento, ou int I, ou int temp, ou calquera que sexa o lugar de variable é, fomos poñendo que na pila. E chamamos iso de unha pila por desa idea de estratificación. Só un tipo de xogos con realidade, o concepto do mesmo. 

Pero resulta que unha pila pode tamén pode ver como unha estrutura de datos, un alternativa a unha matriz, unha alternativa para unha lista ligada. Algo conceptualmente máis interesante que pode ser aplicado a usar un destes cousas, pero é un tipo de estrutura de datos de apoio, en realidade, só dúas operacións. Pero pode engadir máis sofisticado características do que estes. Pero estes son os principios básicos - push e pop. 

E a idea cunha pila é que se eu ten aquí, con ou sen Annenberg saber, unha bandexa xunto co número 9 nel. Entón, simplemente un int. E quero empurrar este para os datos estrutura, que actualmente está baleiro. Considerar este o fondo da pila. Eu levaría ese número 9 ao apilar, e agora está alí. 

Pero a cousa interesante sobre unha pila é que se eu agora quere empurrar algún outro valor, como 17 anos, e eu empurro esta en a pila, eu vou facer o único intuitivo, eu só vou para poñelas exactamente onde nós, seres humanos estaría inclinado a poñelas, na parte superior. Pero o que é interesante agora é, como fago para chegar a 9? Vostede sabe, eu non sen algún esforzo. 

Entón, o que é interesante sobre unha pila é que, ao deseño, é unha estrutura de datos LIFO. Estraña forma de describir last in, first out. Así, o último número na nesta época tiña 17 anos. Entón, se eu queira aparecer algo fóra do conxunto, que só pode ser 17. Polo tanto, hai unha orde obrigatoria de operacións aquí, onde o último elemento en ten que ser o primeiro en saír. De aí a sigla, LIFO. 

Entón, por que isto pode ser útil? Son os seus contextos en que tiña quere unha estrutura de datos como este? Ben, iso certamente foi útil no interior dun ordenador. Entón, usar sistemas operativos claramente esta tipo de estrutura de datos para Stacks. Veremos tamén a mesma idea cando se trata de páxinas web. Entón, esta semana e na próxima semana e ademais, e como comezar a aplicar web páxinas nunha linguaxe chamada HTML, pode realmente usar unha estrutura de datos como isto para determinar se a páxina está formatado correctamente. Porque imos ver todas as páxinas seguen unha especie de xerarquía, un retroceso que, ao final do día, ser un estrutura de árbore debaixo do capó. Así, máis do que en só un bit. 

Pero, por agora, imos propoñer un momento, como poderiamos ir sobre representando o que é unha pila? Déixeme propoñer que Implementar unha pila cun código coma este. Así, unha pila terá no seu interior dúas cousas, unha matriz, chamados de taboleiros, só para ser coherente co demo. E cada un dos elementos desa matriz será un tipo int. Ea capacidade é presuntamente o que? Porque eu non teño escrito o definición completa aquí. 

É, probablemente, o máximo tamaño da matriz. E probablemente é declarado como un forte establecer, na parte superior do ficheiro, algúns tipo de constante como implícito a mera capitalización. Así, a capacidade é definida algures medida que o tamaño máximo posible. Mentres tanto, dentro da estrutura de datos coñecida como unha pila haberá ser un número enteiro só coñecido simplemente como tamaño. 

Entón, se eu fose para representar esta empresa pictoricamente, imos supor que este Cada caixa negra representa a miña stack. Dentro é dúas variables. Entón, eu vou chamar a como unha primeira dimensión. E o segundo que eu vou para debuxar como unha matriz. 

Pero só para manter as cousas en orde, normalmente gustaríame chamar unha matriz como iso, pero é unha especie de bo se corresponde coa realidade, ou coincidir co modelo mental. Entón déixeme en vez de chamar a matriz vertical, o que é xusto, unha vez máis, interpretación do artista. Realmente non importa o que está debaixo do capó. E imos dicir que, por defecto, capacidade será tres. Polo tanto, este será lugar 0, este será de localización 1, o presente será localización 2. 

Se eu subornar con unha bola de estrés, sería alguén que gusta de aparecer e realizar o Suba aquí por un momento? OK, vin o de primeira man. Imos para arriba. Todo ben. Entón, eu creo que é Steven. Imos para arriba. Todo ben. 

Pero supoñamos agora que volver á de inicio estado do mundo onde só declararon unha pila, e é terá unha capacidade de tres. Pero o tamaño non foi determinada. Bandexas aínda non foi determinada. Así, un par de preguntas en primeiro lugar. E déixeme darlle micrófono para que poida participar máis activamente neste proceso. 

Entón, o que está dentro do tamaño neste momento o tempo, se todo o que eu teño feito é declarou unha pila con unha liña de código? 

Steven: Non moito. 

DAVID Malan: OK, non moito. Non sabemos o que está dentro do tamaño, sabemos o que está dentro desa matriz aquí? 

Steven: Só código aleatorio, non? Just - 

DAVID Malan: Si, eu vou chamalo de código, pero aleatoria - 

Steven: Cousas. 

DAVID Malan: Cousas como chou 

Steven: Bits. 

DAVID Malan: Bits, non? Así, os valores de lixo, non? Entón permutacións de 0 e 1 do. Restos de usos anteriores desta memoria. E nós realmente non sei cales son os valores son, polo tanto, normalmente atraelos como puntos de interrogação. 

Entón o primeiro que estamos presuntamente vai querer facer aquí - e deixe-me dar este campo dentro de aí o nome - bandexas. O que temos que presuntamente arrincar tamaño para se queremos comezar a usar esta pila? 

Steven: Bandexa é sub 3. 

DAVID Malan: Entón, Aceptar. Para ser claro, a capacidade é declarado noutros lugares como tres. E iso é o que eu usei para asignar a matriz. Tamaño vai referirse cantos bandexas son actualmente na pila. 

Steven: Cero. 

DAVID Malan: Así debe ser cero. Entón vai adiante, e con calquera dedo, sacar un cero en tamaño. Todo ben. Entón, agora, o que está dentro dese aquí, nós non sabemos. Estes son realmente só valores de lixo. Entón, poderíamos extraer puntos de interrogación, pero imos manter a tarxeta limpa, polo de agora porque non importa o que está aí. Non necesitamos arrincar a matriz para nada, porque se sabe que o tamaño da pila é igual a cero, tamén, nos non debe estar mirando para nada en esa matriz de calquera maneira en Neste punto o tempo. 

Entón, supoña que empurrar o o número 9 na pila. Como debemos actualizar a estrutura de datos dentro desta caixa negra? Cales valores teñen que cambiar? 

Steven: Dentro - o tamaño? 

DAVID Malan: Aceptar. Tamaño debe facer-se o que? 

Steven: arquivo sería un. 

DAVID Malan: Aceptar. Así, o tamaño que se fan un. Así, pode facelo de algunhas formas. Deixe-me dar-lle, agora o seu dedo é unha goma. Todo ben. Entón agora o dedo é un pincel. Todo ben. E agora, o que máis ten que cambiar, obviamente, na estrutura de datos? 

Steven: Nós imos a partir de de abaixo arriba a 9. 

DAVID Malan: 9. OK, Good. Entón, non importa o que está no localización de un ou dous, porque son valores de lixo, pero non debe preocuparse mirando alí porque o tamaño é dicirnos que só o primeiro elemento é realmente lexítimo. Entón agora eu empurrar 17 da lista. Que pasa con esta imaxe? 

Steven: So tamaño está indo a ir a dous. 

DAVID Malan: Aceptar. Está Eraser - oops. Vostede é unha goma. 

Steven: Eraser. 

DAVID Malan: Vostede é un pincel. 

Steven: Brush. 

DAVID Malan: Aceptar. E o que máis? 

Steven: E entón nós - 

DAVID Malan: Nós empuxamos 17. 

Steven: Nós furamos 17 enriba, por iso - 

DAVID Malan: OK, moi bo. 

Steven: - déixase caer. 

DAVID Malan: Todo ben. Está quedando máis fácil. Eu non estou indo a axudar neste momento. Empurre 22. 

Steven: Feito. Tornándose unha goma. Estou me facendo un pincel. E entón eu estou poñendo 22. 

DAVID Malan: 22. Excelente. Así, unha vez máis. Agora estou indo a empurrar para a pila 26. 

Steven: Ooh. Oh Deus. Realmente me colleu desprevenido. 

DAVID Malan: Non fixo ver esta chegada? 

Steven: Non vin isto chegando. Poderiamos capacidade de re-inicio? 

DAVID Malan: Esa é unha boa pregunta. Entón, temos unha especie de nós mesmos pintado nunha esquina aquí. Non hai realmente nada bo fóra a Steven porque temos asignado esa matriz estaticamente, por así dicir, dentro da estrutura de datos. E temos esencialmente codificado que sexa de tamaño tres. Polo tanto, non podemos realmente realocá lo. 

Poderiamos se volvemos, nos redefinido bandexas para ser un punteiro que Axiña, usan a memoria malloc man. Porque, se temos a memoria de o monte vía malloc, nos entón podería libralo. Pero, antes de libera-lo, poderiamos recolocar unha porción maior de memoria, actualizar o punteiro, e así por diante. Pero, polo de agora, iso é realmente o mellor que podemos facer. Push pop son seguramente ter para sinalizar un erro. 

Así, por exemplo, a nosa implantación de impulso podería voltar un booleano que previamente retorno realidade, verdade, verdade. Pero, por cuarta vez, que vai ter para voltar false, por exemplo. Todo ben. Moi ben feito. Parabéns. Vostede gañou a súa bola de estrés hoxe. 

[Aplausos] 

Steven: Grazas. 

DAVID Malan: Grazas. OK, entón iso non parece ser moi dun paso adiante, non? Describimos esta estrutura de datos. Foi interesante, non? Os sistemas operativos gusta. Ao parecer, a web pode facer uso desta, e outras aplicacións aínda. Pero o que unha limitación estúpida que estamos volver a unha especie de semana dous límites onde se fixaron tamaño arrays. 

Polo tanto, hai en realidade un par de formas que poderiamos resolver iso. Poderiamos reservar dinámicamente o array, non polo difícil codifica-lo como eu feito aquí, pero re-declarando iso, só para quedar claro, como algo así. Int * bandexas, non decidir Aínda nunha capacidade. Pero cando declarar a pila noutro lugar no meu código, eu podería entón chamar malloc, obter o enderezo de unha peza de memoria, e eu podía asignar ese enderezo para bandexas. 

E entón, por que é só unha peza de memoria, eu podería continuar a utilizar cadrado a notación de soporte do xeito habitual. Porque unha vez máis, hai unha especie de agasallo equivalente funcional de matrices e bloques de memoria que veñen redor de malloc. Podemos tratar un como o outro mediante a aritmética de punteiro ou notación de corchete. Entón esta é unha visión. 

Pero de que outra forma poderiamos aplicar este mesma estrutura de datos, podendo? Non? Eu sinto que nós só resolveu este problema como hai unha semana. Cal foi a solución a este problema que Steven correu? Listas ligadas entre si, certo. 

O problema é que estamos pintando nos a un canto, alocando anticipadamente moi pouca memoria que logo ter que tratar de algunha maneira co ben, porque non só evitar que emitir por completo? ¿Por que non basta declarar bandexas para ser un punteiro para un nó, ergo unha lista ligada, e despois simplemente reservar novos nós cada vez que Steven necesaria para atender a unha Número na estrutura de datos. 

Así, a imaxe tería que cambiar. Non vai ser tan limpa e tan simple como un conxunto de tres enteiros. Agora será un punteiro a un struct, e que struct vai ter un int e un punteiro próximo. Levará a través dese punteiro a outra estrutura para tal outro tal estrutura. Así, o cadro sería realmente estar un pouco máis confusa. E teriamos frechas amarre todo xuntos. 

Pero iso é bo, correcto, porque vimos como facelo. E unha vez que sentirse cómodo aplicar algo como un linked lista, que vai ter que facer se decide aplicar unha táboa hash coa fío separado para p-set 6, pode usalo como un bloque de construción, ou un ingrediente, ou en scratch dicir, un procedemento, algo que poñer, que creou a súa propia peza do puzzle , Que pode reutilizar. Compensacións que si, pero as posibles solucións que temos realmente visto antes. 

Entón, moitas veces, vostede ve iso todo ano ou dous, cando lanzamentos de Apple algo novo, e todas as persoas tolas liña do lado de fóra da Mazá tenda a mercar o seu marxinal actualizar o hardware. Digo isto, está todo ben, porque Eu son unha desas persoas. Entón, que tipo de estrutura de datos pode representar esa realidade? 

Ben, imos chamalo dunha fila, nunha liña. So British chamaría tanto tipicamente un cola de todas as maneiras, polo que é un bo nome. E as dúas operacións que a cola apoia imos chamar a enfileirar operación e unha operación de eliminación da fila, que son similares en espírito de push e pop. É só unha especie de diferente en convención, o que estamos chamando eses. Pero para enfileirar algo significa para engadir ou inserir-lo na estrutura de datos. Para desenfileirar medios para eliminar-lo. Pero, mentres unha pila era un dos datos LIFO estrutura, unha fila é un primeiro, por primeira vez a estrutura de datos. 

Se é a primeira persoa na cola, será a primeira persoa en chegar fóra de liña e mercar o seu novo dispositivo. Imaxina o quão chat estas persoas sería se a Apple en canto usou unha pila, a exemplo, para aplicar a colleita up do seu novo xoguete. Entón filas teñen sentido, por suposto, e podemos pensar en todo tipo de aplicacións, presuntamente, a filas, especialmente cando quere xustiza. Entón, como podemos implementar las como unha estrutura de datos? 

Ben, eu propoño que poidamos Debe facelo deste xeito. Entón, eu vou agora ter números. Entón, imos manter as cousas simples e non necesariamente falar en termos de bandexas. Só números que a xente de comezara. Capacidade vai, unha vez máis, resolver o número total de persoas que poden estar en Nesta liña, como tres ou calquera outro valor. 

Pero propoño que eu teño para manter o control non só do tamaño da cola, cantas cousas están na mesma. Así, o tamaño é o tamaño actual, a capacidade é o tamaño máximo. Así de novo, a nomenclatura por convención. Por que eu teño un int adicional dentro dunha cola para seguir o que está en fronte da liña? Por que eu teño que facer iso neste caso? 

Ben, como é esta foto vai cambiar? Eu probablemente pode reutilizar máis da imaxe. Déixeme ir adiante e borrar o que está aquí. Nós imos dar a este un pouco nome diferente aquí. Imos nos librar dos 17, imos nos librar do 9, imos nos librar do 3. E imos engadir unha outra cousa. Propoño que eu teño para manter o control de a fronte da lista, que é só será un int ben. E nós imos mantelo simple. Ningunha lista ligada por agora. 

Imos admitir que imos bater-se contra este límite. Pero o que quero ver pasar esta vez? Entón, supoñamos que eu dalle o primeiro persoa ven na liña, e é o número 9. Temos bolas de estrés. Podo roubar, digamos, dúas ou tres persoas? Un, dous, tres? Imos para arriba. Dereito de fronte, xa que nós imos facer este rápido. 

Cada un de vós é agora será un neno fan na cola de Apple. Non vai recibir o hardware de Apple a finais deste aínda. Todo ben. Entón, vostede é o número 9, está número 17, número 22. Estes son números arbitrarios, como IDs de estudante ou outros enfeites. E en só un momento, imos comezar para comezar a engadir as cousas. E eu vou correr o consello aquí neste momento. 

Polo tanto, neste caso, eu xa inicializar diante para ser - En realidade, eu realmente non me importa o que o diante é porque o tamaño é igual a cero. Polo tanto, este pode moi ben ser un punto de interrogación. Estes son todos os puntos de interrogación. Entón, agora nós imos realmente comezar a ver algúns persoas facendo cola na tenda. 

Entón, se o número 9, que é o primeiro alí 05:00, vai adiante e aliñar, ou na noite anterior. Aceptar. Entón agora 9 é aquí. Así 9 é diante da lista. Entón, eu estou indo a ir adiante e actualizar o tamaño dos datos actuais estrutura para non ser máis 0, pero para ser 1. Vou poñer 9 na cabeza da lista. Déixeme ir adiante e cambiar a pantalla así podemos ver por nós aquí. 

E agora o que quero para poñer adiante? Vou manter o control que o cabeza da cola agora está na posición 0. Porque o que está próximo vai pasar? Ben, supoño que agora enfileirar 17 tamén. Entón hop en liña alí. E, de novo, o tipo de porta ao tenda estará aquí. Entón agora eu engade 17. E aínda que estes faces están bloqueando da pantalla, que é OK, porque podemos velo aquí. Sentímolo. 

Audiencia: Podemos cambiar - 

DAVID Malan: Non, iso é OK. É enorme alí enriba. Así, é agora 17 dentro da cola. Eu teño actualizar o que campos agora que? OK, en definitiva tamaño. E como a cabeza? OK, non. Fronte non debe cambiar, porque a diferenza dunha pila, quere manter a equidade. Entón, se 9 quedou en primeiro lugar, queremos 9 para ser o primeiro en saír da liña e para a tenda. 

De feito, imos ver iso. Antes de inserir 22, imos dalle dequeue 9. Cal é o seu nome? 

Audiencia: Jake. 

DAVID Malan: Jake vai para ser será agora. Entón comeza a entrar na tenda. E finxir que a tenda está alí. Entón, agora o que ten - dit-dit-dit! Que ten que pasar agora? Decisión de deseño. Entón, non é un mal instinto, pero - cal é o seu nome? 

Audiencia: David. 

DAVID Malan: David. Entón, o que fixo David? Estaba intentando resolver de corrixir os datos estrutura e movemento a partir da súa localización na antiga ubicación do Jake. E iso é bo, se estamos dispostos para aceptar isto como unha detalle de implementación. Pero, primeiro, imos actualizar os datos estrutura antes de facelo. Porque eu non estou gustando a idea de todo a xente desprazando nesta liña. 

Non é gran cousa se David fai un paso, pero, de novo, creo que volve cando tivemos oito voluntarios na escenario e fixemos como inserción tipo, no que tivemos que comezar movéndose a todos arredor. Isto ten cara, non? Isto faime encoller sobre o gran de n, gran O de n ao cadrado de novo. Non está sentindo como un resultado ideal. 

Entón imos actualizar isto. Así, o tamaño da cola xa non é 2. Agora é simplemente un. Pero agora podo actualizar algo Non actualizar antes, a cabeza da lista. Podería só dicir, é que unha situación? Polo tanto, agora temos valor de lixo aquí, valor de lixo aquí, e David no medio dese lixo. Pero, a estrutura de datos aínda está intacto. 

E, de feito, eu nin preciso cambiar ex número un do Jake 9, porque quen lle importa. Eu teño bastante información agora no tamaño que sei que hai unha persoa en esa cola. E sei que esa persoa está na posición 1, e non 0. Non estou contando. Así, un ben. Así, a estrutura de datos aínda é OK. 

Ben, o que ocorre? Imos enfileirar - cal é o seu nome? 

Audiencia: Callen. 

DAVID Malan: Callen. Imos enfileirar unha Callen, e 22 xa está na cola. Entón, agora o que ten que cambiar aquí? Fronte non vai cambiar, obviamente. Tamaño vai pasar a ser 2 novo. E 22 acaba aquí, 9 aínda está presente, pero é efectivamente un valor de lixo agora. É só un remanescente de Jake pasado. 

Entón agora o que pasa se Eu desenfileirar David? Unha última operación, dequeue David. Poderiamos cambiar, pero propoño imos facer tan pouco traballo como sexa posible. Agora a miña estrutura de datos vai atrás en tamaño de 2 a 1. Pero a cabeza da cola agora pasa a ser 2. Eu non teño cambiar estas cifras pero só porque son só os valores de lixo. 

Pero, agora, o que pasa? Supoñamos que me enfileirar, 26? Eu sinto que eu pertenzo aquí. Entón, eu estou sendo enfileirado. Entón eu medio que pertenzo aquí. E aínda que non fai ben apreciar este aspecto no escenario, porque temos moito espazo, eu debería non estar aquí, por que? 

Audiencia: Está fóra dos límites. 

DAVID Malan: Correcto. Estou fóra dos límites. Eu indexado alén do límites desta matriz. Realmente debería estar nun dos tres localizacións posibles. Agora, onde é máis natural para ir? Propoño que alavancou unha semana un truco. O operador mod, porcentaxe. Porque estou tecnicamente en pé localización 3, pero fago 3 capacidade mod, para 3, un sinal de porcentaxe, 3 - capacidade é 3. ¿Que é iso? Cal é o resto cando dividir 3 por 3? 0. 

Así que me pon foron Jake era, o que é realmente bo. Entón, agora a posta en marcha desa cousa vai ser un pouco de dor de cabeza. É realmente só unha liña de dor de cabeza, de código. Pero polo menos agora hai lixo valor aquí, pero hai dous ints lexítimos aquí. E eu afirmo que agora fixemos exactamente o que cómpre facer, sempre que podemos cambiar o que Jake valor sería 26. 

Agora temos información suficiente aínda para manter a integridade esta estrutura de datos. Nós aínda estamos medio fóra de sorte cando nós quere inserir catro ou máis Total elementos, pero podo polo menos facer moito uso eficiente da presente constante tempo, en realidade. Non se preocupe con cambio todos, como inclinación de David era. 

Calquera dúbida sobre pilas, ou esta cola? 

Audiencia: É a razón pola cal precisa de tamaño para que vostede sabe onde se ten unha persoa? 

DAVID Malan: Exactamente. Eu teño que saber o tamaño da matriz por que eu teño que saber exactamente como Moitos deses valores son lexítimas, e para que eu poida atopar onde colocar a seguinte persoa. Exactamente. O tamaño é - En realidade, nós non actualizar iso aínda. Eu me engadido aos 26 anos. O tamaño é agora, non un, senón dous. Entón, agora este feito me axuda a atopar o cabeza de lista, o que non é 0, non 1, pero é 2. A parte dianteira da lista é de feito o número 22. Porque quedou en primeiro lugar, polo que debe ser autorizados a entrar na tenda antes de min, malia visual estou máis preto da tenda. 

Todo ben? Unha salva de palmas para estes faces e nós imos deixar los de alí. 

[Aplausos] 

DAVID Malan: eu podería deixar manteña a bandexa. Puidemos ver o que pasa se quere, pero quizais non. Todo ben. Entón, o que agora é que iso nos deixa? Ben, deixe-me propor que hai un algunhas outras estruturas de datos que poderían comezar a engadir ao noso kit de ferramentas que van realmente ser moi, moi relevante como nós mergullo cousas web. Que á súa vez, ten algún tipo de conexión a árbores, baixo a forma de algo chamado DOM, documento modelo de obxecto. Pero imos ver máis de que en pouco tempo. 

Déixeme propoñer que por definición chamar árbore agora o que se pode saber como máis dunha árbore de familia, onde ter algún antepasado en raíces da árbore. A matriarca patriarcal ou na o cumio da árbore. Sen o seu cónxuxe, neste caso. Pero agora temos que chamaremos nenos, que son os nós que penden fóra o fillo esquerdo ou o dereito do neno, frechas como descrito aquí. 

Noutras palabras, unha estrutura de datos en árbore en ordenador, unha árbore ten cero ou máis nós. Se ten polo menos un nodo, que se chama raíz. É as cousas visualmente que trazamos na parte superior. E este nodo, como calquera outro no, pode ter cero, unha ou dúas, ou tres, ou cantos fillos o estrutura de datos soporta. Neste caso, a raíz, o almacenamento valor un, ten dous fillos, 2 e 3, así que normalmente chamamos 2 á esquerda neno e 3 o neno correcta. 

E entón, cando chegamos a 5, 6 e 7, 6 pode ser chamado o fillo do medio. Se ten catro fillos, el queda confuso. Entón, deixe de usar este tipo de acceso verbalmente. Pero é realmente só unha árbore xenealóxica. E as follas aquí son os nós que eles mesmos non teñen fillos. Fican fóra da parte inferior da árbore. 

Entón, como podemos implementar unha árbore que ten só dous fillos maxima? Imos chamalo dunha árbore binaria. Bi novo significando dous, neste caso, como co binario. E, polo tanto, pode ter cero, unha ou os dous fillos maxima. 

Vou propoñer que imos aplicar o no a esta estrutura, cun int n, e logo, dous enlaces, un chamado á esquerda, un chamado á dereita. Pero estes son só bo convencións arbitrarias. E o que é bo momento, especialmente se tipo de dificultade conceptual con recursão, ou pensar que non era realmente unha solución a nada, especialmente se puidese sen memoria. Agora que estamos a falar de datos estruturas e algoritmos que permiten nos a atravesar e manipula-los, Acontece que a recursividade volta en unha moito máis atractivo se non é bo camiño. 

Entón, iso eu propoño é a implementación dunha función de investigación. Dadas dúas entradas - polo que pense nisto como unha caixa negra. Dadas dúas entradas, N, un int, e un punteiro para unha árbore, un punteiro para unha no, ou realmente a raíz dunha árbore, eu alegación de que esta función pode volver verdadeira ou falsa, isto valor n É dentro desta árbore. 

O que ten dentro desa caixa negra? Así, catro ramas. O primeiro só verifica. Se a árbore é nula, simplemente voltar falso. Se non o houbera ningún nodo, non hai n, non hai ningún número, só volverá false. Se, con todo, n, o valor que está a buscar a, é menor que a árbore frecha ne só para quedar claro, o que quere dicir cando Escribo árbore e, a continuación, a frecha notación, n? Exactamente. Isto significa que desreferenciava punteiro chamado árbore. Vaia alí, e, a continuación, entrar dentro que nó e conseguir o seu campo chamado n. E, a continuación, comparar o n real que se pasou para Investigación contra el. 

Así, se n é menor que o valor n no propio nodo da árbore, así, O que significa isto? Iso non significa nada a primeira vista. Non? Así como cando ten un conxunto de valores, pode gusta de aplicar binario investigación como unha forma de división e conquistar. Pero o presuposto de que necesitamos facer para investigación binaria para traballar en conxunto no libro de teléfono e exemplos anteriores? 

Como ser clasificados. Entón, imos refinar a definición de árbore aquí para non ser só unha árbore, que pode ter calquera número de fillos. Non é só unha árbore binaria, o que pode ter 0, 1 ou 2 maxima. Pero, como unha árbore de busca binaria, ou CEST, que é só un xeito elegante de dicir a árbore binaria de xeito que de cada nodo fillo esquerdo, presente, é menos que o nó. Correo neno o dereito de cada nó, se está presente, é máis grande do que o propio nó. 

Polo tanto, noutras palabras, se fose deseñar a saída da árbore, as cifras son coidadosamente equilibrado como este, para que se ten 55 como a raíz, de 33 anos pode ir á súa esquerda, xa que é inferior a 55. 77 pode ir ao seu dereito, xa que é superior a 55. Pero, agora, entender, a mesma definición, é unha definición recursiva verbalmente, cómpre pedir 33. 33 do fillo esquerdo debe ser menor que, e dereito do neno de 33, 44, debe ser maior que iso. 

Polo tanto, esta é unha árbore de busca binaria, e Propoño, usando un pouco de recursão, agora podemos atopar n. Así, se n é menor que o valor de n, que é No actual, eu estou indo a ir adiante e punto, por así dicir, e só devolver calquera que sexa a resposta é de busca de n en fillo esquerdo da árbore. Teña en conta unha vez máis, esta función só espera unha estrela no, un punteiro para un nó. Entón, por suposto eu só podo facer árbore frecha para a esquerda, o que levará me a outro nodo. Pero o que é este nó? 

Ben, de acordo con esta declaración, esquerda é só un punteiro, de xeito que só Significa que eu estou pasando para a función de busca un indicador diferente, en particular o que supón un árbore do meu fillo esquerdo. Polo tanto, neste caso, o punteiro a 33, se esta é a nosa mostra de entrada obstante, se n é maior que o valor de n en No actual na árbore, entón eu estou indo a ir adiante e punto na outra dirección e dicir, eu non sabe se este valor n está na árbore, pero eu sei que si é, é a miña sector dereito, por así dicir. Entón deixe-me chamar recursivamente buscar, pasar un n de novo, pero pasando unha punteiro para o meu fillo dereito. 

Noutras palabras, se eu estou actualmente en 55 e eu estou buscando 99, sei que 99 é maior que 55, entón como eu Rompín o libro de teléfono desde hai semanas e nós foi á dereita, do mesmo xeito somos nós Vai estar ben aquí. E eu non sei se é a miña dereita neno, e non é, de 77 está aí, pero Sei que é nesa dirección. Entón, eu chamo de busca no meu fillo dereito, 77, e que a figura de investigación a partir alí se 99 deste arbitraria exemplo é realmente alí. 

Senón, o que é o caso final? Se a árbore é nula é un caso. Se non for menor que a corrente do nodo valor é outro caso. Se n é maior que o actual valor do nodo é un terceiro caso. Qué é o cuarto e último caso? Creo que estamos fóra dos casos, non? Debe ser, no que n é o nodo actual que estou. 

Entón, se eu estou buscando 55 neste momento na historia, ese sector da árbore volvería verdade. Entón, o que é interesante aquí é que nós en realidade, a diferenza de semana pasado, nós medio de ter dous casos base. E eles non teñen a estar na parte superior. O principio é un caso base, porque se o árbore é nulo, non hai nada que facer. Só ten que voltar un disco codificado valor false. 

A rama inferior é unha especie de defecto, polo cal se teña comprobado para nulo, temos comprobado que debe ser á esquerda, pero non debe ser, temos Comprobarase se debe estar seguro, pero non debe ser, claro, ten que ser exactamente onde estamos. Isto é un caso base. Polo tanto, hai dous casos recursivas entalado alí no medio. Pero eu podería escribir isto en calquera orde. Eu só penso que tipo de pareceume natural primeiro comprobar un posible erro, a continuación, comproba a esquerda, a continuación, asegúrese de ben, entón supoñer que está no nodo está realmente a buscar. 

Entón, por que isto pode ser útil? Así, verifica-se - e deixe-me ir a un teaser aquí que está na web. Nós imos comezar a usar non é unha linguaxe de programación en principio, pero a linguaxe de reserva. A linguaxe de marcación que é ser un similares en espírito á programación linguaxe, pero el non lle dá o capacidade de expresarse de forma lóxica. El só lle dá a capacidade de expresar-se estruturalmente. 

Onde quere poñer algo na páxina, a páxina web? Cal é a cor que quere facer isto? O tamaño do tipo de letra que quere facer isto? Que palabras o que realmente quere na páxina web? Así que esta é unha linguaxe de marcación. Pero, entón, imos presentar moi rapidamente JavaScript, que é un verdadeiro linguaxe de programación. Moi semellante sintaticamente no aspecto a C, pero vai ter un bo, máis potente, máis características de fácil utilización. 

E unha das frustracións neste punto no semestre é que imos pronto aplicar Speller en moito menos liñas de código, utilizando outras linguaxes que a propia C permite, pero por motivo de en breve imos entender. Este será o primeiro nesta páxina web. Será completamente por baixo do esperado, o primeiro que facemos. Vai simplemente dicir: Ola mundo. Pero se nunca viu antes, este é HTML, HyperText Markup Language. 

Se vai a unha determinada opción de menú máis calquera navegador, en calquera páxina web en a Internet, podes ver o HTML que algunhas persoas escribiron para crear esta páxina web. E probablemente non parece tan breve ou tan puro coma este. Pero vai seguir o estándar destes corchetes abertos e barras e letras e números. potencialmente 

Penso en darlle un teaser do que vai ser capaz de facer despois de tomar CS50. Déixeme ir cs.harvard.edu / roubo, páxina de inicio nosa propia Rob Bowden. Fíxoo por nós. Así, en breve vai ser capaz de facelo. E tamén, o que escoitou esta mañá - o que escoitou esta mañá - 

[Hamster baile music] 

- Será capaz de facer isto. Que nos espera o mércores. Imos velo axiña. 

[Hamster baile music] DAVID Malan: Na seguinte CS50 -