[Música tocando] DAVID Malan: Este é CS50. E isto é tanto o inicio eo end-- como literally-- case o final de seis semanas. 

Eu penso que eu ía compartir un pouco dun feito divertido. Eu puxei iso desde un datos do semestre pasado definido. Debe lembrar que pedimos que en cada forma conxunto p se asistiu en liña ou se xa asistiu en persoa. E aquí están os datos. Entón, hoxe foi moi previsible. Pero queriamos pasar un pouco de tempo con vostede, con todo. Alguén quere conjecturar por que isto gráfico é tan irregular, ata abaixo, arriba abaixo, de forma consistente? Que cada un dos picos e depresións representan? 

Audiencia: [inaudível] DAVID Malan: De feito. E máis divertidamente, Deus me libre, temos unha charla o venres ao comezo do semestre, iso é o que vemos suceder. Entón, hoxe, nós participamos dun pouco máis sobre estruturas de datos. E, para darlle máis dun sólido modelo mental para problemas en cinco, que agora está fóra. Erros de ortografía, no cal, nós imos entregarlle un ficheiro de texto algúns 100.000 máis palabras en inglés, e vai ter para descubrir como para cargalos de forma intelixente en memoria, na memoria RAM, utilizando-se algúns datos estrutura da súa elección. 

Agora, unha estrutura de datos podería ser, pero probablemente non debe ser, a lista ligada bastante simplista, que introducimos última vez. E unha lista ligada tiñan polo menos unha vantaxe sobre unha matriz. ¿Que é unha vantaxe de unha lista ligada sen dúbida? 

Audiencia: Inclusión. 

DAVID Malan: Inclusión. O que quere dicir con iso? 

Audiencia: En calquera lugar ao longo lista [inaudível]. 

DAVID Malan: Good. Así, pode introducir un elemento sempre quere no medio da lista sen ter que embaralhar calquera cousa, que concluíu, na nosa clasificación discusións, non é necesariamente unha cousa boa, porque leva tempo para realmente moverse todos os seres humanos cara á esquerda ou cara á dereita. E así, cunha lista ligada, pode só reservar con malloc, un novo nodo, e logo, actualizar un par de pointers-- dous, tres operacións max-- e somos capaces de encaixar alguén en calquera lugar nunha lista. 

Que máis se vantaxoso aproximadamente unha lista ligada? Si? 

Audiencia: [inaudível] DAVID Malan: Perfecto. Perfecto. É moi dinámico. E que non está cometendo, anticipadamente, ata certo tamaño fixo anaco de memoria, como tería para con unha matriz, o cabeza de que é que pode reservar os nós só en demanda utilizando así só a cantidade de espazo como o que realmente precisa. En contraste con un array, pode accidentalmente reservar moi pouco. E despois é só ir ser unha dor no pescozo para recolocar unha nova matriz maior, copiar todo máis, liberar a matriz vella, e despois pasar sobre a súa empresa. Ou peor, pode reservar forma máis memoria do que realmente precisa, e así vai ter unha moi matriz escasamente poboada, por así dicir. 

Así, unha lista ligada dálle estas vantaxes de dinamismo e flexibilidade con insercións e borrados. Pero certamente debe haber un prezo a pagar. De feito, un dos temas explotada no cuestionario de cero era un par de os trade-offs vimos ata agora. Entón, o que é un prezo pagado ou a desvantaxe dunha lista ligada? Si. 

Audiencia: Sen acceso aleatorio. 

DAVID Malan: Sen acceso aleatorio. Pero quen lle importa? De acceso aleatorio non soa convincente. 

Audiencia: [inaudível] DAVID Malan: Exactamente. Se queres ter un certo algorithm-- e déixeme realmente propoñer busca binaria, en particular, que é un que usei moito bit-- se non ten acceso aleatorio, non pode facelo aritmética simple de como atopar o elemento do medio e saltando dereito a ela. Non ten que comezar na primeira elemento e linearmente busca esquerda á dereita, se quere atopar a media ou de calquera outro elemento. 

Audiencia: Probablemente ocupa máis memoria. 

DAVID Malan: ocupa máis memoria. Onde é que adicional custa vindo na memoria? 

Audiencia: [inaudível] DAVID Malan: Exactamente. Neste caso aquí, tivemos unha lista encadeada de números enteiros, e aínda estamos dobrando a cantidade de memoria necesitamos tamén por almacenar eses punteiros. Agora menos de un gran negocio como súas estruturas quedan maiores e está almacenando non un número, pero quizais un estudante ou algún outro obxecto. Pero o punto seguro permanece. E así un certo número de tarefas en listas ligadas foron chamados eran grandes O lineal de n--. Cousas como inserción ou busca ou exclusión no caso dun elemento Aconteceu o final da a lista se está clasificado ou non. 

Ás veces pode ter sorte e en límites tan baixos sobre estas operacións pode tamén ser de tempo constante, se está sempre mirando para o primeiro elemento, por exemplo. Pero, ao final, que prometeu para alcanzar o Santo Graal de estruturas de datos, ou algúns destes aproximación, por medio de constante de tempo. Podemos atopar elementos ou engadir elementos ou eliminar elementos dunha lista? Veremos en breve. E verifícase que un dos mecanismos que estamos comezará a usar hoxe, utilización anual en p establecer cinco, é realmente moi familiar. Por exemplo, se se trata dun grupo libros de exame, cada un dos cales ten un alumno de primeira nome e apelidos, e eu busca-las a partir de ao final dun exame, e todos eles son moi moi nunha orde aleatoria, e queremos ir sobre a clasificación estes exames, de modo que, unha vez clasificado é só moito máis fácil e máis rápido para entrega-los de volta para fóra para os alumnos por orde alfabética. Que os seus instintos ser para unha pila de exames como este? 

Ben, se vostede é como eu, vostede verás que iso é m, entón eu vou especie de poñer isto en, se esta é a miña mesa ou o meu piso, onde Estou espallando cousas out-- ou miña matriz realmente-- Podería poñer todo o Ms alí dentro. Oh. Velaquí un A. Entón eu podería Como poñer os aquí. Oh. Aquí está outro A. Vou poñer isto aquí. Velaquí un Z. Aquí está outro M. E así Podería comezar a facer pilas como esta. E entón quizais eu ía máis tarde e tipo de moi detallista-ly tipo as pilas individuais. Pero o punto é que eu quedaría na entrada que eu son destro e gustaríame facer un calculado decisión con base nesa entrada. Se comeza con A, colocar-lo alí. Se comeza con Z, poñelas sobre alí, e todo máis. 

Polo tanto, esta é unha técnica que é xeralmente coñecido como hashing-- H-A-S-h-- o que xeralmente significa tomar como de entrada e usando que a entrada para calcular un valor, xeralmente, un número, e que número é o índice para un dispositivo de almacenamento recipiente, como unha matriz. Polo tanto, noutras palabras, eu podería ter un función de hash, como fago na miña cabeza, que, se eu vexo alguén é nome que comeza con A, Eu estou indo a mapear que a cero na miña cabeza. E se eu vexo alguén con Z, eu son vai mapear que a 25 na miña cabeza e logo, poñer isto en o último máis pila. 

Agora, se pensar en non meu cerebro Pero un programa C, o que os números poderían confiar para lograr este mesmo resultado? Noutras palabras, se tiña o carácter ASCII A, como é posible determinar o balde para poñelas? Probablemente non quere poñelas balde de 65 anos, que Sería como alí sen unha boa razón. Onde queiras poñer un en termos do seu valor ASCII? Onde quere facer para o seu ASCII valor para chegar a un balde de forma máis intelixente para poñelas? 

Audiencia: Minus A. 

DAVID Malan: Yeah. Así, menos un ou menos especialmente 65 se é un capital A. Ou 98 se é unha minúscula a. E así que nos permiten, moi de xeito sinxelo e moi aritmeticamente, poñer algo en un balde así. Entón non é que realmente facemos este ben mesmo cos quizzes. 

Así, pode lembrar que circulou seu Nome ensino compañeiro na capa. E os nomes do TF organizáronse estas columnas en orde alfabética, Ben, cren ou non, cando todos 80 máis de nós reuníronse na outra noite para grao, o último paso no noso proceso de clasificación é para picar os cuestionarios nunha gran espazo de chan no [inaudível] e establecer quizzes de todos para fóra exactamente na orde dos seus TF de nomes na portada, xa entón é moito máis doado para nós a procura a través de que o uso lineal buscar ou algún tipo de intelixencia para un TF para atopar o seu ou quizzes dos seus alumnos. 

Entón, esa idea de hashing que verá é moi poderoso é realmente moi banal e moi intuitiva, moi parecido, quizais, e dividir conquista foi a semana cero. Eu avance rápido á hackathon un par de anos. Este foi Zamyla e un par de outros alumnos saúdo persoal como eles entraron. E tivemos unha morea de dobradura mesas alí con etiquetas de nome. E nós tiñamos as etiquetas de nome organizado con como os Como por alí eo ZS alí. E así un dos TFS moi intelixente escribiu isto como as instrucións ao día. E a semana 12 do semestre este todo fixo sentido perfecto e todos sabía o que facer. Pero sempre que teño enfileirados no mesmo xeito, está aplicando o mesma noción dun hash. Entón, imos formalizar-lo un pouco. Aquí é unha matriz. El está deseñado para ser un pouco gran só para describir, visualmente, para que poidamos poñer cordas en algo como isto. E esa matriz é claramente de tamaño 26 total. E a cousa chámase mesa de forma arbitraria. Pero esta é só capitulación dun artista que unha táboa hash pode ser. 

Así, unha táboa hash agora vai ser unha estrutura de datos de nivel superior. Ao final do día estamos a piques de ver que pode aplicar unha táboa hash, que é moi parecido a liña de facturación a unha hackathon moi parecido con este táboa usada para clasificar os libros de exame. Pero unha táboa hash é especie de agasallo de alto nivel concepto que podería usar unha matriz debaixo do capó para implementar lo, ou pode usar unha lista de lonxitude, ou mesmo quizais algunhas outras estruturas de datos. E agora que é a toma theme-- algúns destes ingredientes fundamentais como un array e este edificio bloquear agora dunha lista de lonxitude e ver o que máis podemos construír enriba de quen, como ingredientes nunha receita, tornándose cada vez máis resultados finais interesantes e útiles. 

Así, coa táboa hash podemos implementar lo na memoria pictoricamente como este, pero como pode realmente ser codificado enriba? Ben, quizais simplemente como é iso. Se a capacidade en todas as tapas, é só algúns constant-- por exemplo 26, para 26 letras do alphabet-- Podería chamar de miña mesa variable, e eu podería dicir que eu vou poñer estrelas de char alí, ou cadea. Por iso, é tan sinxelo coma iso se quere aplicar unha táboa hash. E, con todo, iso é realmente só unha matriz. Pero, de novo, un hash táboa é agora o que imos chamar un tipo abstracto de datos que é só unha especie de estratificación conceptual na parte superior de algo máis mundano agora como un array. 

Agora, como é que imos sobre a resolución de problemas? Ben, en principio eu tiven o luxo de ter espazo suficiente mesa aquí para que eu puidese poñer o quizzes en calquera lugar que eu quería. Entón, como pode ir aquí. Zs pode ir aquí. MS pode ir aquí. E entón eu tiven un pouco de espazo extra. Pero iso é un pouco de un dereito de fraude agora, porque esta táboa, se realmente penso niso como unha matriz, é só será de preto de tamaño fixo. 

Entón, tecnicamente, se eu tirar se cuestionario doutro alumno e ver, oh, esta persoa de nome comeza cun A tamén, Eu medio que quero poñer-lo alí. Pero así que eu colocar-lo alí, se esta táboa de feito representa unha matriz, Eu vou estar substituíndo ou sobrepasar quen cuestionario deste alumno é. Non? Se este é un array, só unha cousa pode ir en cada unha destas células ou elementos. E entón eu medio que teño de escoller. 

Agora antes de que eu tipo de enganado e fixo iso ou eu só unha especie de empilhados Los por riba da outra. Pero iso non vai voar no código. Entón, onde eu podería poñer o segundo alumno cuxo nome é A, se todo o que eu tiña é este dispoñible espazo de táboa? E eu usei tres slots e que Parece que hai só uns doutros. O que podería facer? Audiencia: [inaudível] DAVID Malan: Yeah. Quizais imos mantelo simple. Non? Ela non encaixa onde quero poñelas. Entón, eu vou poñelas tecnicamente, onde un B ía. Agora, por suposto, eu estou empezando a pintar-me nunha esquina. Se eu chegar a un estudante cuxo nome é, en realidade, B, agora B será movido algo para adiante, como pode pasar, si, se este é un B, agora ten que ir aquí. 

E por iso esta moi rapidamente podería chegar a ser problemático, pero é unha técnica que, en realidade, se refire como lineal de sondaxe, en que considerar só o seu matriz de ser ao longo da liña. E só tipo de sonda ou inspeccionar cada elemento dispoñible buscando un lugar dispoñible. E así que atopa un, large-lo alí dentro. 

Agora, o prezo a ser pago agora para esta solución é o que? Temos unha matriz de tamaño fixo, e cando inserir nomes para el, polo menos inicialmente, o que é o tempo de execución de inserción para poñer os alumnos quizzes nos baldes non? Big O de que? 

Audiencia: n. DAVID Malan: Eu oín gran O de n. Non é certo. Pero nós imos provocar unha separación por que en só un momento. O que máis podería ser? 

Audiencia: [inaudível] DAVID Malan: E déixeme facelo visualmente. Entón, supoñamos que esta é a letra S. 

Audiencia: É unha. DAVID Malan: É unha. Non? Esta é unha matriz, que significa que temos acceso aleatorio. E se pensamos desa como cero e iso como 25, e entendemos que, oh, aquí está a miña entrada S, Eu certamente podo converter S, un carácter ASCII, a un número correspondente entre cero e 25 e, a continuación, inmediatamente poñelas onde pertence. 

Pero, claro, así que eu chegar ao segunda persoa cuxo nome é A ou B ou C finalmente, se eu usei o lineal enquisa como a miña solución, o tempo de execución inserción no peor caso é realmente vai transformarse en que? E eu oín-lo aquí correctamente desde o principio. Audiencia: [inaudível] DAVID Malan: Así é, de feito, xa n ten unha suficientemente grande conxunto de datos. Así, por unha banda, se a matriz é grande abondo e os seus datos é escasa o suficiente, obter este tempo constante bonito. Pero así que comezar a quedando máis e máis elementos, e só estatisticamente que comeza máis persoas coa letra Unha como o seu nome ou a letra B, que podería potencialmente transformarse en algo máis lineal. Entón, non é absolutamente perfecto. Entón, poderíamos facer mellor? 

Ben, o que foi a nosa solución antes cando nós quere ter máis dinamismo do que algo así como unha matriz permitido? Audiencia: [inaudível] DAVID Malan: O que nós presentamos? Si. Así, unha lista ligada. Ben, imos ver o que un conectado lista pode facer por nós no seu lugar. Ben, deixe-me propor que deseñar a imaxe do seguinte xeito. Agora este é un diferente imaxe dun exemplo a partir dun texto diferente, de feito, que é, en realidade, usando unha matriz de tamaño 31. E este autor simplemente decidiu botar cordas non en base a nomes da persoa, pero en base ás súas datas de nacemento. Independentemente do mes, figuraron se naceu o primeiro día dun mes ou o día 31 dun mes, o autor vai botar en base nese valor, de forma a difundir os nomes un pouco máis que 26 puntos pode permitir. E quizais sexa un pouco máis uniforme que ir coas letras do alfabeto, porque está claro que hai, probablemente, máis persoas no mundo con nomes que comezar con unha que seguramente algunhas outras letras do alfabeto. Entón quizais iso sexa un pouco máis uniforme, asumindo unha distribución uniforme de bebés a través dun mes. 

Pero, por suposto, iso aínda é imperfecto. Non? Estamos tendo colisións. Varias persoas nesta estrutura de datos aínda son tendo a mesma data de nacemento, polo menos vostede independentemente do mes. Pero o que o autor fixo? Ben, parece que temos un array no lado da man esquerda tomada en vertical, pero iso é só interpretación dun artista. Non importa que dirección ten deseñar unha matriz, que aínda é un array. ¿Que é iso unha serie de parecer? 

Audiencia: lista encadeada. 

DAVID Malan: Yeah. Parece que é unha matriz de lista ligada. Entón, de novo, a este punto de tipo de usar esas estruturas de datos agora como ingredientes a máis solucións interesantes, pode perfectamente ter un fundamentais, como unha matriz, e logo tomar algo máis interesante como unha lista ligada e mesmo combina-los nun mesmo estrutura de datos máis interesante. E, de feito, iso tamén sería ser chamado unha táboa hash, polo que a matriz é realmente a táboa hash, pero que ten táboa hash correntes, por así dicir, que pode crecer ou psiquiatra con base no número de elementos que quere inserir. 

Agora, nese sentido, o que é o tempo de execución agora? Se eu queira inserir alguén cuxo aniversario é o 31 de outubro de onde é que el ou ela vai? Todo correcto. Na parte inferior, onde el di que 31. E iso é perfecto. Ese foi o tempo constante. Pero o que se atopar alguén cuxo aniversario é, imos ver, Outubro, novembro, 31 de decembro? Onde é que el ou ela vai? Mesmo. Dúas etapas aínda. Isto é constante, aínda que, non é? Todo correcto. No momento en que ela é. Pero, no caso xeral, canto máis a xente que agregan, probabilisticamente, imos para obter máis e máis colisións. 

Agora iso é un pouco mellor, porque técnicamente Agora miñas cadeas poderían estar en o peor caso canto tempo? Se eu inserir n persoas a este máis estrutura de datos sofisticado, n persoas, no peor dos casos vai ser n. Por que? 

Audiencia: Por se todo o mundo ten o mesmo aniversario, están indo a ser unha liña. DAVID Malan: Perfecto. Pode ser un pouco artificial, pero realmente, no peor caso, se todo o mundo ten o mesmo aniversario, dadas as entradas que ten, vai ter un masivamente cadea longa. E así, podería chamalo de un Hash Table, pero realmente é só unha enorme lista ligada unha morea de espazo desperdiçado. Pero, en xeral, se asumirmos que polo menos, os aniversarios son uniform-- e probablemente non é. Eu estou facendo iso. Pero se asumirmos, por a causa da discusión que son, entón, en teoría, se esta é a representación verticais da matriz, así, entón espero que está se ve cadeas que son, vostede sabe, aproximadamente a mesma lonxitude, onde cada un dos deles representa un día do mes. 

Agora, se hai 31 días no mes, isto significa que o meu tempo de carreira realmente é grande O de n máis de 31, que sente mellor que linear. Pero o que era un dos nosos compromisos de algunhas semanas sempre hai que se trataba de expresar o tempo de execución dun algoritmo? Basta só ollar para o termo de orde superior. Non? 31 é sempre útil. Pero iso aínda é grande O de n. Pero un dos temas do conxunto de problemas de cinco será a recoñecer que absolutamente, asintótica, teoricamente esta estrutura de datos non é mellor que só unha lista ligada maciza. E, de feito, no peor dos casos, este táboa hash pode transformarse en que. 

Pero no mundo real, con nós seres humanos que os propios Macs ou PC ou o que quere e están en execución no mundo real software en datos do mundo real, algoritmo que vai preferir? Aquel que toma medidas finais ou á que leva n dividido por 31 pasos para atopar algunha peza de datos ou para buscar información? Quero dicir, absolutamente as 31 marcas unha diferenza no mundo real. É 31 veces máis rápido. E nós, os seres humanos son, sen dúbida, vai apreciar isto. 

Así, entender a dicotomía en realidade existe entre falando cousas teoricamente e asintótica que definitivamente ten valor como vimos, pero no mundo real, se se preocupa só facendo o feliz humano para as entradas xerais, pode moi ben querer aceptar o feito de que, si, é dicir lineal, pero é 31 veces máis rápido que se pode lineal. E mellor aínda, non só temos que facer algo arbitrario como a data de nacemento, poderiamos pasar un pouco máis tempo e intelixencia e pensar sobre o que poderiamos facer, dado o nome dunha persoa e quizais a súa data de nacemento para combinar os ingredientes para descubrir algo que é verdadeiramente máis uniforme e menos irregular, por así dicir que esta foto actualmente suxire que podería ser. Como podemos aplicar isto no código? Ben, deixe-me propor que só pedir algún sintaxe temos utilizado un par de veces ata agora. E eu estou indo a definir un nó, que de novo é un termo xenérico para uns poucos recipiente para algunha estrutura de datos. Vou propoñer que unha secuencia que vai dentro. Pero imos comezar a tomar aquelas rodinhas fóra agora. 

Non hai máis biblioteca CS50 realmente, a menos que quere usalo para o seu final, proxecto, que é bo, pero agora estamos indo para tirar a cortina e dicir que é só unha estrela de char. Así, a palabra non será o nome da persoa en cuestión. E agora eu teño unha ligazón aquí ao seguinte nodo para que estes representan cada un dos nós na cadea, potencialmente, dunha lista ligada. 

E agora como fago para declarar propia táboa de hash? ¿Como declarar toda esta estrutura? Ben, en realidade, moi parecido que eu usei un punteiro para só o primeiro elemento dunha lista antes, do mesmo xeito podo só dicir Eu só teño unha morea de punteiros para aplicar esta táboa hash todo. Vou ter un array chamada de táboa para a táboa hash. Será de capacidade tamaño. É así que moitos elementos poden caber nel. E cada un deses elementos neste matriz vai ser unha estrela no. Por que? Ben, por esta foto, o que eu son aplicar a táboa de hash como principalmente no inicio é só esa matriz que temos deseñado en vertical, cada un de cuxos cadrados representa un punteiro. Que aqueles que teñen barras a través deles son só nulo. E os que teñen frechas que van cara á dereita son punteiros reais para nós reais, ergo o inicio dunha lista ligada. 

Entón, aquí, entón, é como podemos aplicar unha táboa hash que aplica o encadeamento separado. Agora podemos facer mellor? Todo ben que prometín a última vez que poderiamos conseguir tempo constante. E eu medio que lle deu constante de tempo aquí, pero logo non dixo realmente constante de tempo porque aínda é dependente do total número de elementos está introducindo en a estrutura de datos. Pero supoña que fixemos iso. Déixeme volver á pantalla aquí. Permítanme tamén proxectar esta aquí enriba, claro da pantalla, e supoño que eu fixen iso. Supoña que eu quería introducir o nome Daven en na miña estrutura de datos. 

Entón, quero introducir unha cadea Daven na estrutura de datos. E se eu non usar un Hash Table, pero eu uso algo que é máis do tipo árbore como unha árbore xenealóxica, onde tes algunha raíz no nós e follas superiores e, a continuación, que ir para abaixo e para fóra. Supoñamos, entón, que eu quere inserir Daven de en que é actualmente unha lista baleira. Vou facer o seguinte: Eu son vai crear un nó desta familia árbore-como estrutura de datos que parece algo parecido con iso, cada unha das cales rectángulos ten, digamos, para agora 26 elementos nel. E cada unha das células nesta matriz vai para representar a letra dun alfabeto. 

En concreto, eu estou indo para o tratamento este é A, entón B, entón C, entón D, este aquí. Entón, iso vai efectivamente representar a letra D. Pero para introducir todos Daven de nome eu teño que facer un pouco máis. Entón, eu estou indo primeiro para mestura, por así dicir. Vou ollar para a primeira letra en Daven do que é, obviamente, unha D, e eu estou indo a reservar un nó que parece como isto-- un gran rectángulo grande abondo para caber todo o alfabeto. 

Agora D está feito. Agora A. D-A-V-E-N é o obxectivo. Entón agora o que vou facer é esta. Así que comecei a notificación D non hai ningún punteiro alí. É valores de lixo, no momento, ou eu podería arrincar a null. Pero déixeme continuar esta idea de construír unha árbore. Déixeme reservar un deses nodos que contén 26 elementos nel. 

E vostede sabe o que? Se este é só un nó na memoria que Eu creei con malloc, usando unha struct como veremos en breve, Vou facer isso- Vou debuxar unha frecha de a cousa que representase D abaixo para este novo nodo. E agora, por primeira vez o seguinte carta en nome de Daven, V-- D-A-V-- vou ir adiante e deseñar outro nodo como este, polo que, os elementos de V, que aquí imos chamar de berros instance--. Non imos sacar alí. Vai aquí. 

Entón nós imos consideran que se trata V. E entón aquí imos índice abaixo de V ao que imos considerar E. E entón dende aquí imos vaia ter un destes nós aquí. E agora temos unha pregunta para responder. Eu teño algunha maneira indican que estamos na fin da cadea Daven. Entón, eu podería deixar lo nulo. 

Pero o que se ten de Daven nome completo tamén, que é, como xa dixemos, Davenport? Entón, o que si é Daven realmente unha substring, un prefixo dunha secuencia moito máis tempo? Non podemos simplemente permanentemente dicir nada vai para ir alí, porque podiamos nunca, introduce unha palabra como Davenport para esta estrutura de datos 

Entón, o que poderiamos facer é no canto tratar cada un destes elementos Tendo como quizais dous elementos dentro deles. Un deles é un punteiro, de feito, como eu veño facendo. Así, cada unha destas caixas non é só un teléfono móbil. Pero e se o cumio um-- do un fondo será nulo, xa que non hai Davenport aínda. E se o cumio é algún valor especial? E iso vai ser un pouco difícil deséñase la deste tamaño. Pero creo que é só unha marca de verificación. Consulte. D-A-V-E-N é unha secuencia nesta estrutura de datos. 

Mentres tanto, se eu tivese máis espazo aquí, eu podería facer P-O-R-T, e eu podería poñer facturar o no que ten a letra T ao final. Polo tanto, este é un masivamente estrutura de datos de aparencia complexa. E a miña letra certamente non axuda. Pero se eu quería introducir algo outra cousa, considerada o que fariamos. Se quixésemos poñer David na, nós seguen a mesma lóxica, D-A-V, pero agora eu apuntaría a próxima elemento non desde E, aínda que a partir de I a D. Polo tanto, non será máis nós nesta árbore. Nós imos ter chamada malloc máis. Pero eu non quero facer unha desorde completa da imaxe. Entón, imos ollar a unha vez que foi pre-formuladas así con non punto, punto, puntos, pero só matrices abreviados. Pero cada un dos nós nesta árbore-se aquí representa o mesmo coisa-- unha serie de Ray tamaño 26. 

Ou, se quere ser realmente bo momento, o que se o nome de alguén como un apóstrofo, imos supoñer que cada nodo ten realmente como 27 índices en que, non só 26. Entón, iso agora será un dos datos unha estrutura chamada trie-- T-R-I-e. Unha trie, que supostamente é historicamente un nome intelixente para unha árbore optimizado para de recuperación, o que, por suposto, é soletrado cun I-E por iso é trie. Pero esa é a historia da trie. 

Así, unha trie é estes datos en árbore estrutura como unha árbore xenealóxica que en definitiva se comporta así. E aquí é só un exemplo dunha todo morea de nomes doutras persoas. Pero a cuestión agora na man é o que ten gañamos a través da introdución dun indiscutibelmente máis estrutura de datos complicado, e un, francamente, que utiliza unha gran cantidade de memoria. 

Porque aínda que, no momento, eu só estou usando punteiro D e A e V e Es e Ns, Estou perdendo unha peza de moita memoria. Pero onde eu pasar un recurso, Eu tendo a non gañar de volta outro. Entón, se eu estou gastan máis espazo, o que é, probablemente, a esperanza? Que eu estou gastan menos co que? Audiencia: Menos tempo. DAVID Malan: Equipo. Agora, por que pode ser iso? Ben, o que é a inserción tempo, en termos de gran ó momento, dun nome como Daven ou Davenport ou David? Ben, Daven era de cinco etapas. Davenport sería nove etapas, polo que sería máis algúns pasos. David sería cinco pasos ben. Polo tanto, estas son de formigón números, pero certamente hai un límite superior sobre o lonxitude do nome de alguén. E, de feito, no problema conxuntos de cinco especificación, imos propoñer que é algo que é de 40 caracteres e tantos. 

Realista, ninguén ten un nome infinitamente longo, o que quere dicir que a lonxitude dun nome ou a lonxitude dunha cadea que pode estar seguro de que o estado de estrutura é sen dúbida o que? É constante. Non? Pode ser unha gran constante como 40 e poucos anos, pero é constante. E iso non ten ningunha dependencia de cantos outros nomes están nesta estrutura de datos. Noutras palabras, se I quería agora introducir Colton ou Gabriel ou Rob ou Zamyla ou Alison ou Belinda ou outros nomes do equipo en datos estrutura, é o tempo de execución de introducir outros nomes será en todo impactaram pola forma como moitos outros elementos son na estrutura de datos xa? Non é. Non? Porque nós estamos efectivamente usando esta táboa hash de multi-capa. E o tempo de execución de calquera destas operacións non é dependente do número de elementos que se atopan na estrutura de datos ou que son, finalmente, indo estar na estrutura de datos, pero na lonxitude do que especificamente? 

A secuencia de estar inserida, o que fai este asintótica constante tempo-- gran O dun. E, francamente, só en o mundo real, este significa introducir o nome de Daven leva como cinco etapas, ou Davenport nove etapas, ou David cinco etapas. Isto é moi danado pequenos tempos de execución. E, de feito, iso é moi O bo, especialmente cando non é dependente do total número de elementos de alí. Entón, como podemos aplicar esta tipo de estrutura en código? É un pouco máis complexo, senón que é só unha aplicación de bloques de construción básicos. Eu estou indo a axustar nos nó como segue: booleano chamado word-- e esta podería chamarse de calquera cousa. Pero o representa booleano o que eu deseño como unha marca de verificación. Si. Esta é o extremo dunha corda nesta estrutura de datos. 

E, por suposto, a estrela nodo non está referíndose a nenos. E, de feito, así como unha árbore de familia, ten consideraría os nós que son colgado da parte inferior de algúns dos pais elemento a ser nenos. E así os nenos vai ser unha matriz de 27, a unha 27th sendo só para apóstrofo. Estamos indo para clasificar de caso especial que. Entón pode que seguro nomes con apóstrofo. Quizais ata guión debe vaia alí, pero ver xuntos p 5 só coidado sobre letras e apóstrofos. 

E entón como é que representa a propia estrutura de datos? Como representar a raíz desta trie, por así dicir? Ben, así como cunha lista ligada, ten precisa dun punteiro para o primeiro elemento. Cunha trie só precisa dun punteiro para a raíz desta trie. E a partir de aí pode botar o seu camiño cada vez máis fondo para todos os outros nós na estrutura. Entón simplemente con esta lata representamos que struct. 

Agora Meanwhile-- Oh, pregunta. 

Audiencia: Cal é palabra bool? 

DAVID Malan: palabra bool é só nesta encarnación C do que eu describín nesa caixa aquí, cando Comecei dividindo cada un dos elementos en dúas pezas da matriz. Un deles é un punteiro ao seguinte nodo. A outra ten que ser algo así como unha caixa de verificación dicir que si, hai unha Daven palabra que termina aquí, porque non queremos, no momento, Dave. 

Aínda que Dave será un palabra lexítima, non está no trie Aínda. E D non é unha palabra. E D-A non é unha palabra ou un nome. Así, a marca de verificación indica só unha vez acadar este nodo é o traxectoria anterior de personaxes en realidade, unha secuencia de carácteres que inseriu. Entón, iso é todo o bool non está facendo por nós. 

Calquera outras preguntas sobre intentos? Si. 

Audiencia: Cal é a superposición? E se ten un Dave e un Daven? DAVID Malan: Perfecto. E se ten un Dave e un Daven? Entón, se nós inserimos, digamos, un apelido, para David-- Dave-- D-A-V-E? Esta é realmente super sinxelo. Entón nós só imos levar catro etapas. D-A-V-e. E o que eu teño que facer, xa que eu bati cuarta nodo? Só tes que ir comprobar. Xa está preparado para ir. Feito. Catro pasos. Constante de tempo asintótica. E agora que xa indicaron que tanto Dave e Daven son cadeas na estrutura. Entón, non é un problema. E teña en conta como a presenza Daven de non facelo levar máis tempo ou menos tempo para Dave e viceversa. 

Entón o que máis podemos facer? Usamos esta metáfora antes bandexas de representar algo. Pero parece que a pila de taboleiros é realmente demostrativo doutro abstracto de datos type-- unha estrutura de datos de nivel superior que, ao final do día é só como unha matriz ou unha lista ligada ou algo máis mundano. Pero é unha máis interesante concepto conceptual. Unha pila, como estes Bandexas aquí en Mather, son xeralmente chamados só que-- unha pila. 

E, neste tipo de estrutura de datos ten dúas operations-- ten un chamado de impulso para engadindo algo para a pila, como poñer outra bandexa atrás sobre o cume da pila. E logo pop, o que significa que tomar o máis alto para fóra da bandexa. Pero o que é importante sobre unha pila é que el ten esa característica curiosa. Como o equipo de comedor son rearranjar as bandexas para a próxima comida, o que vai ser verdade sobre como os alumnos interactuar con esta estrutura de datos? Audiencia: Eles están indo estalar un fóra. DAVID Malan: Eles van estalar un fóra, espero que o cumio. Se non, é só unha especie de estúpida para percorrer todo o camiño ata o fondo. Non? A estrutura de datos realmente non permite incorporarse a bandexa inferior, polo menos, facilmente. Entón hai ese curioso propiedade dunha pila que o último elemento é vai ser o primeiro en saír. E os científicos da computación chaman este LIFO-- último a entrar, primeiro en saír. E realmente ten aplicacións interesantes. Non é necesariamente tan obvio como algúns outros, pero pode, de feito, ser útil, e pode, de feito, ser aplicado nun par de formas diferentes. 

Entón, un, e de feito, imos me para mergullo niso. Imos facelo no seu lugar. Imos ollar un que é case o mesma idea, pero é un pouco máis xusto. Non? Se vostede é un destes nenos fans ou nenas que realmente lle gusta de produtos de Apple e espertou ás 3h00 para aliñar nalgunha tenda para obter a última iPhone, vostede podería cola coma este. 

Agora a cola é moi deliberadamente nomeado. É unha liña porque non hai algunha xustiza a el. Non? Sería unha especie de sugado se ten chegou primeiro na Apple Store pero é efectivamente o bottommost bandexa porque os empregados de Apple, a continuación, estalar a última persoa que realmente ten na liña. Entón, pilas e colas, aínda funcionalmente son tipo do same-- é só esta colección de recursos que é vai medrar e shrink-- existe este aspecto xustiza a el, polo menos, no mundo real, onde as operacións se exercita son fundamentalmente diferentes. Un stack-- unha fila rather-- dise ter dúas operacións: cola de n e d fila. Ou pode chamalos unha serie de cousas. Pero só quere capturar a noción de que unha é a suma de e unha definitiva, é subtraindo. 

Agora baixo o capó, tanto a pila e unha cola podería ser aplicado como? Non imos entrar no código de xa que o nivel máis elevado idea é unha especie de máis evidente. Quero dicir, o que os humanos fan? Se eu son a primeira persoa en Apple Almacenar e esta é a porta de entrada, vostede sabe, eu vou estar aquí. E a seguinte persoa se ve aquí. E a seguinte persoa se ve aquí. Entón, o que estrutura de datos préstase a unha fila? 

Audiencia: A cola. DAVID Malan: Ben, unha cola. Claro. Que máis? 

Audiencia: Unha lista ligada. 

DAVID Malan: un conectado lista que podería aplicar. E unha lista ligada é bo porque despois pode crecer arbitrariamente longa en oposición para ter un número fixo de persoas na tenda. Pero quizais un número fixo de prazas é lexítimo. Porque se eles só teñen como 20 iPhones o primeiro día, quizais eles só precisan dunha matriz de tamaño 20 para representar esa cola, que é só para dicir agora, xa que comezar a falar sobre estes problemas de nivel superior, pode implementar lo en calquera número de formas. E non hai, probablemente, só vai ser un trade off no espazo e no tempo ou só na súa propia complexidade do código. 

Que tal unha pila? Ben, unha pila, vimos tamén podería ser só estas bandexas. E podería aplicar esta unha matriz. Pero nalgún momento, se usa unha matriz, o que vai pasar coas bandexas estás a poñer para abaixo? Todo correcto. Só vai poder ir tan alto. E eu creo que están en Mather de feito, en que a apertura do receso. Entón, en realidade, é case como Mather está a usar unha matriz de tamaño fixo, porque só pode caber tantas bandexas en que a apertura de a parede abaixo xeonllos das persoas. E, de xeito que se pode Dise que unha matriz, pero nós certamente podería aplicar esta de modo máis xeral, con unha lista ligada. 

Ben, o que dicir de outra estrutura de datos? Déixeme puxar arriba outro visuais aquí. Algo así como que tal esta aquí? Por que pode ser útil para non ter algo tan extravagante como unha trie, que vimos que tiña eses nós moi anchas, cada un dos cales está nunha matriz? Pero o que se facer algo máis simplemente, como unha árbore xenealóxica da vella escola, cada un de cuxos nós aquí é só almacenar un número. En vez de un nome ou un descendente é só almacenar un número como esta. 

Ben, o argot que usan en estruturas de datos é dous intentos e árbores, onde unha trie, de novo, é só unha cuxos nós son matrices, aínda é o que se pode usar da escola de clase cando fixo unha familia tree-- follas ea raíz da árbore e nenos do pais e irmáns dos mesmos. E poderiamos aplicar unha árbore, por exemplo, como simplemente como este. Unha árbore, coma se un nó, un dos estes círculos que contén un número, non vai ter un punteiro, pero dúas. E así que engadir un segundo punteiro, ten agora pode realmente facer tipo de datos bidimensional estruturas en memoria. Moi parecido un bidimensional array, pode ter tipo de bidimensional listas ligadas, pero os que seguen un patrón onde non hai ciclos. É verdadeiramente unha árbore cunha xeito avó aquí e despois para arriba algúns pais e fillos e netos e bisnetos. e así por diante. 

Pero o que é realmente interesante sobre iso tamén, só para provoca-lo con algo de código, recordo de recursão algún tempo, no que escribir unha función que chama a si mesmo. Esta é unha fermosa oportunidade para aplicar algo como recursão, porque considerar isto. 

Esta é unha árbore. E eu teño sido un pouco anal coa forma como Engada os números enteiros para a rúa. Tanto é así que ten unha especial nome-- unha árbore de busca binaria. Agora nós xa escoitou falar de binario buscar, pero pode traballar cara atrás desde o nome desta cousa? Cal é o estándar de como eu inseridos os números enteiros para esta árbore? Non é arbitraria. Hai algún defecto. Si. 

Audiencia: Os menores de esquerda. 

DAVID Malan: Yeah. Os menores están á esquerda. As maiores son na dereita. De tal forma que unha afirmación verdadeira é unha pai é maior que o seu fillo esquerdo, pero menos que o seu fillo dereito. E só iso é mesmo un definición verbal recursiva porque pode aplicar ese mesma lóxica para cada nodo E só Bottoms a fóra, un caso base, se ganas, cando bate un dos as follas, por así dicir, onde unha licenza non ten fillos aínda. 

Agora, como pode atopar o número 44? Podería comezar na raíz e dicir, hm. 55 non é 44 Entón eu quero ir dereito ou quero ir á esquerda? Ben, obviamente quere ir esquerdo. E así é como o teléfono exemplo libro en busca binaria de modo máis xeral. Pero estamos implementar lo agora un pouco máis dinámica que unha matriz pode permitir. E, de feito, se quere ollar no código, a primeira vista, con certeza. Parece que unha morea de liñas. Pero é ben sinxelo. Se quere aplicar unha función chamada investigación cuxo propósito na vida é a procura dun valor como n, un enteiro, e que pasou nun pointer-- un enlace para o no das raíces, ao contrario, de que árbore da cal podes acceder todo o máis, observe como directamente pode aplicar a lóxica. Se árbore é nulo, obviamente non está alí. Nós só retornar falso. Non? Se entrega-lo nada, non hai nada alí. 

Logo, se n é inferior a árbore frecha n-- agora arrow n, lembrar que introducimos Super brevemente o outro día, e que só significa de-referencia a punteiro e ollar para o campo chamado n. Entón isto significa ir alí e ollar para o campo chamado n. Entón, se n, o valor que se recibe, é menos en que o valor do enteiro árbores, onde quere ir? Á esquerda. 

Entón, observe a recursividade. Estou returning-- non é verdade. Non falsa. Estou volvendo calquera que sexa a resposta é a partir dunha chamada para min, pasando un n de novo, o que é redundante, pero o que é un pouco diferente agora? Como eu estou facendo o problema menor? Estou pasando como a segunda argumento, non a raíz da árbore, pero o fillo esquerdo neste caso. Entón, eu estou pasando o fillo esquerdo. 

Por outra banda, se n é maior que o no Actualmente estou mirando, Eu busco o lado dereito. Outra cousa, se a árbore non é nulo, e Se o elemento non está á esquerda e non é a dereita, o que é marabillosas o caso? Nós realmente atopamos o no en pregunta, e así volvemos verdade. 

Entón, nós só arranhamos a superficie agora algunhas destas estruturas de datos. No conxunto de problemas de cinco vai explotar estes aínda máis lonxe, e será dado o seu proxecto elección como ir sobre iso. O que me gustaría terminar sobre é só un segundo teaser 30 do que nos espera a próxima semana e alén. 

Como nós begin-- sorte podes penso-- nosa transición lenta do mundo da C e menor detalles de implementación nivel, a un mundo no que podemos tomar para seguro que alguén ten, finalmente, aplicado estes datos estruturas para nós, e imos comezar a entender o mundo real significa de implantación programas baseados na web e sitios máis xeralmente e tamén a propia seguridade implicacións que nós só comezaron a rabuñar a superficie do. Aquí está o que nos espera os días que virán. 

[REPRODUCIÓN DE VIDEO] 

-El Veu cunha mensaxe, cun protocolo de todos os seus propios. El veu para un mundo de cruel firewalls, routers indiferente, e perigos moito peores que a morte. El é rápido. El é forte. El é o TCP / IP, e el ten o seu enderezo. "Guerreiros da rede." [FIN REPRODUCIÓN DE VIDEO] DAVID Malan: Na próxima semana. Imos velo axiña. [REPRODUCIÓN DE VIDEO] -E Agora, "Pensamentos Profundos" por Daven Farnham. -David Comeza sempre conferencias con: "Todo ben." Por que non, "Aquí está a solución ao conxunto de problemas esta semana " ou "Estamos dando a todos vostedes un A?" [Risas] [FIN REPRODUCIÓN DE VIDEO]