[Música tocando] ANDI Pengo: Benvido á semana 6 da sección. Nós desviado o noso patrón tempo sección deste martes tarde para esta linda mañá de domingo. Grazas por todos os que uniuse a min hoxe, pero en serio, unha salva de palmas. Isto é un ben grande esforzo. Eu case non mesmo facelo Se o tempo, pero foi Aceptar. Entón eu sei que todos vós que acaba de facer-lo para o quiz. Primeiro de todo, benvido ao a outra cara disto. En segundo lugar, imos falar sobre iso. Imos falar sobre o quiz. Imos falar sobre como está facendo na clase. Vai estar ben. Teño súas probas para vostede a finais de aquí, por iso, se vostedes queren tomar un ollar para el, totalmente ben. Entón, rapidamente, antes de comezar, o axenda para hoxe é o seguinte. Como verás, estamos queima basicamente rápida través de unha chea de estruturas de datos realmente, realmente, realmente rápido. Así, como tal, non será hoxe de super interactivo. Vai ser só me especie de berrar cousas que, e se eu confundir-lo, se estou indo demasiado rápido, deixe-me saber. Son só diferentes datos estruturas, e como parte do seu pset para este semana, vai ser solicitada para aplicar un deles, quizais dúas eles-- dous deles na súa pset. OK, entón eu estou indo só para comezar con algúns anuncios. Nós imos pasar por riba de pilas e colas máis en profundidade do que o que fixemos antes do quiz. Nós imos pasar por riba conectado lista de novo, unha vez máis, máis en profundidade que o que tivemos antes do quiz. E entón nós imos falar sobre haxix mesas, árbores e intentos, que son todos moi necesario para o seu pset. E entón nós imos pasar por riba de algúns consellos útiles para pset5. OK, entón cuestionario 0. A media era de 58%. Foi moi baixa, e así vós todos fixo moi, moi ben, segundo con iso. Moi ben, regra de ouro é se está dentro dun desvío estándar da media especialmente xa que estamos nun salvo sección de confort, está totalmente ben. Está no camiño certo. A vida é boa. Sei que é asustado pensar que Eu teño como un 40% neste quiz. Vou sair clase. Eu prometer a vostede, non está vai fallar a clase. Está totalmente ben. Para aqueles de vostedes que teño máis a media, impresionante, impresionante, como, en serio ben feito. Eu telos comigo. Sinto-se libre para vir buscalos ao final da sección. Deixe-me saber se tes calquera cuestións, preguntas con eles. Se sumarmos a súa puntuación mal, deixe-nos saber. OK, entón pset5, este é realmente un semana estraño para Yale no sentido que a nosa pset débese Mércores ao mediodía, incluíndo o día de atraso, polo que é, en realidade, teoricamente debido martes ao mediodía. Probablemente ninguén terminou en martes ao mediodía. Isto é totalmente bo. Nós imos ter o horario de oficina esta noite, así como na noite de onte. E todas as seccións desta semana vai de feito, pode converter talleres, tan a gusto para pop en calquera sección que quere, e eles van ser unha especie de mini-pset talleres para axuda sobre iso. Así, como tal, esta é a única sección onde estamos material didáctico. Todas as outras seccións centrarase exclusivamente na axuda ao pset. Si? Audiencia: Onde están as horas de expediente? ANDI Pengo: Horario de atención tonight-- Oh, boa pregunta. Eu creo que o horario de oficina esta noite están en Teal ou en Commons. Se comprobar en liña CS50 e vai para o horario de expediente, debe haber un programa que dille onde todos son. Sei tanto esta noite ou mañá é cerceta, e eu creo que podemos ter commons para a outra noite. Non estou seguro. Boa pregunta. Comprobe en CS50. Cool, calquera dúbida sobre o programa para a próxima como tres días? Eu prometer a vostedes como David Dito isto, esta é a parte superior do outeiro. Vostedes están case alí. Só tres máis días. Chegar alí, e entón todos nós imos descender. Nós imos ter un descanso agradable CS-free. Nós imos voltar. Imos mergullar na web programación e desenvolvemento, cousas que son moi divertido comparación para algúns dos outros Serie de exercicios. E vai ser frío, e imos ter moita diversión. Teremos máis doces. Desculpem-me por doces. Esquecín de doces. Era unha mañá áspera. Entón vostedes están case alí, e eu estou realmente orgulloso de vós. OK, entón apilar. Que amaba a pregunta sobre Jack e as súas vestiduras a proba? Ninguén? OK, iso é bo. Entón, basicamente, como pode imaxe de Jack, este cara aquí, Quere aproveitar a roupa fóra do cumio da pila, e pon-lo de volta para a pila despois que está feito. Así, deste xeito, nunca parece estar quedando para a parte inferior da apilar na súa roupa. Polo tanto, este tipo de describe a estrutura de base de datos de como unha pila é aplicada. Esencialmente, pense en un pila como calquera pila de obxectos onde poñer as cousas a arriba, e entón pop-los para fóra do cumio. Entón LIFO é a sigla que nos gusta para use-- último In, First Out. E así durar para arriba da pila é o primeiro que sae. E así os dous termos nos gusta de asociar que son chamados push e pop. Cando empurrar algo ao pila, e poñer-la de volta. E entón eu creo que esta é unha especie de concepto abstracto para aqueles de vostedes que queren ver como un aplicación efectiva deste no mundo real. Como moitos de vostedes teñen escrito un ensaio quizais como unha hora antes do vencemento, e excluíu accidentalmente un enorme anaco del, como accidentalmente? E entón o que facer control que usan para poñer-lo de volta? Control-Z, si? Control-Z, de xeito que a cantidade de veces que Control-Z salvou a miña vida, salvo miña bunda, cada vez que é aplicado a través dunha pila. Esencialmente toda a información que está no seu documento de Word, é empurrado e bateu a gusto. E así, esencialmente, sempre que eliminar calquera cousa, poñer-la de volta. E entón se precisa del de novo, empurralo lo, que é o Control-C fai. E función mundo tan real de estrutura de datos como simple pode axudar coa súa vida cotiá. Así, un struct é o camiño que realmente crear unha pila. Nós escriba definir struct, e, a continuación, chamamos iso de pila na parte inferior. E dentro do conxunto, temos dous parámetros que pode, esencialmente, manipular, polo que temos de char capacidade cordas estrela. Todo o que está a facer é a creación dunha matriz que pode almacenar o que queiras que podemos determinar a súa capacidade. Capacidade é a cantidade máxima de elementos que podemos poñer en esta matriz. tamaño int é o contador que mantén o control de cantos elementos están actualmente na pila. Entón nós pode seguir, A, tanto como gran a pila é real, e, B, canto desa pila enchemos porque nós non queremos rebosar sobre o que é a nosa capacidade. Así, por exemplo, esta linda pregunta era sobre o seu quiz. Esencialmente, como imos empurrar sobre o cumio dunha pila. Moi sinxelo. Se ollar para el, imos camiñar por este. Se [inaudível] size-- Teña en conta que, sempre que quere acceder calquera parámetro dentro dunha estrutura, fai o nome do struct.parameter. Neste caso, s é o nome da nosa stack. Queremos acceder ao tamaño da mesma, polo que facemos s.size. Así, se o tamaño non é igual capacidade ou desde xa que é menos que a capacidade, quere ía traballar aquí. Quere acceder ao interior do seu stack, entón s.strings, e está indo a poñer este novo número que quere inserir alí. Nós só dicir que imos querer inserir int n na pila, poderíamos facer s.strings, corchetes, s.size iguala n. Porque o tamaño é onde nós Están na pila se nós estamos indo a empurrar Lo, nós só acceder onde queira que o tamaño sexa, o plenitude corrente da pila, e nós empurrar o int n nel. E entón nós queremos estar seguro de que tamén estamos incrementando tamaño do n, para que poidamos manter o control de nós temos engadida unha cousa extra para a pila. Agora temos un tamaño maior. Será que isto aquí ten sentido todos, loxicamente como funciona? Era unha especie de rápido. Audiencia: Pode pasar por riba os s.stringss.strings [s.size] de novo? ANDI Pengo: Correcto, entón o que fai s.size actualmente dar? Audiencia: É o tamaño actual. ANDI Pengo: Exactamente, polo que a índice actual que o noso tamaño é en, e por iso queremos poñer o novo enteiro que queremos introducir s.size. Isto ten sentido? Porque s.strings, todo isto é é o nome da matriz. Todo o que é acceder ao matriz dentro da nosa estrutura, e así, se queremos poña n en que o índice, podemos simplemente acceder a ela utilizando soportes s.size. Legal. Todo ben, pop, eu Pseudocódigo para fóra para vós, pero concepto similar. Isto ten sentido? Se o tamaño é maior que cero, entón sei que quere tomar algo porque se o tamaño non é maior que cero, entón ten nada na pila. Así, só quere executar este código, el só pode pop se hai algo que estalar. Así, se o tamaño é maior que 0, que menos o tamaño. Nós diminuír o tamaño e, a continuación, voltar o que está dentro dela, porque estalado, queremos acceso todo o que está almacenado no índice do cume da pila. Todo ten sentido? Se eu fixen convosco escribir isto, se vós poder escribilo lo? OK, podedes xogar con el. Non te preocupes se non obtelo. Non temos tempo para codificar Lo hoxe, porque temos ten unha morea de estas estruturas para percorrer, pero, esencialmente, pseudocódigo, moi, moi semellante ao empurrar. Só ten que seguir ao longo da lóxica. Asegúrese de que está accedendo todo o características da súa estrutura correctamente. Si? Audiencia: Será que estes diapositivas e esa cousa toda ser ata hoxe-ish? ANDI Pengo: Sempre, si. Vou tentar poñer isto como unha hora despois. Vou enviar correo-e David, David vai poñelas como unha hora despois diso. OK, entón, a continuación, nos movemos para estoutro estrutura de datos encantador chamada de cola. Como podedes ver aquí, un cola, para os británicos entre nós, todo isto é unha liña. Así, a diferenza do que Pensas que é unha pila, unha fila é o que loxicamente que pensa que é. É realizado polas regras do FIFO, que é first in, first out. Se é a primeira un na liña, está que o primeiro sae da liña. Entón, o que nos gusta chamar este é dequeueing e enqueueing. Se queremos engadir algo a nosa cola, nós enfileirar. Se queremos retirar da cola, ou tomar algo lonxe, nós retirar da cola. Así mesmo sentido que somos tipo de a creación de elementos de tamaño fixo que pode almacenar certa cousas, pero nós tamén podemos pasar a onde estamos poñendo parámetros dentro deles a base do que tipo de funcionalidade que queremos. Entón, pilas, queriamos a última un, N para ser o primeiro en saír. Cola é que queremos o primeiro para ser o primeiro para fóra. Así, o tipo struct definir, como se pode ver, é un pouco diferente desde o que foi a pila porque non só temos que manter o control de onde o tamaño é actualmente, tamén queremos manter o control da cabeza así como onde estamos actualmente. Entón, eu creo que é máis fácil se eu sacar iso. Entón, imos imaxinar que temos unha fila, entón imos dicir que a cabeza está ben aquí. O xefe da liña, imos só dicir que é actualmente alí, e queremos introducir algo na cola. Vou chamar ao tamaño esencialmente é o mesmo que a cola, o fin da cola é sempre que o seu. Nós só dicir que tamaño é aquí. Así como un practicable introducir algo nunha cola? O índice queremos poñer onde queremos inserir. Se este é o inicio da súa cola e este é o fin de todo ou o tamaño del, onde é que imos quere engadir o seguinte obxecto? Audiencia: [inaudível] ANDI Pengo: Exactamente, quere engadir Lo dependendo escribiu el. Ou este é en branco ou que está baleiro. Entón quere engadir lo probablemente aquí porque, se o tamaño é-- se estes son todos completo, quere engadir lo aquí, non? E así que é, á vez moi, moi simple, non é ben sempre correcto porque a principal diferenza entre unha cola e unha pila é que a cola pode de feito, ser manipulado de xeito que os cambios de cabeza dependendo de onde queiras o inicio da súa suxestión para comezar. E, como resultado, a súa cola tamén vai cambiar. E entón bótalle un ollo este código agora. Como vostedes tamén foron convidados a escribir sobre o quiz, enqueue. Quizais nós imos falar a través por a resposta era o que era. Eu non podía encaixar esta liña nun, pero, esencialmente, este anaco de código debe estar nunha liña. Gastar como 30 segundos. Bótalle un ollo, e mira por que esta é a forma que é. Moi, moi semellante struct, moi, moi estrutura semellante á do anterior apilar agás, quizais, unha liña de código. E que unha liña de código determina a funcionalidade. E iso realmente diferencia unha fila dunha pila. Quen queira tomar unha facada para explicar por que ten ten esa cousa complicada aquí? Vemos o retorno do noso marabilloso módulo amigo. Como vostedes virá logo de recoñecer na programación, case en calquera momento precisas algo para involucrar calquera cousa, módulo será a forma de facelo. Entón, sabendo que, alguén quere para tratar de explicar esta liña de código? Si, as respostas son aceptado e benvido. Audiencia: Está falando comigo? ANDI Pengo: Si. Audiencia: Oh, non me desculpe. ANDI Pengo: OK, entón imos camiñar por este código. Entón, cando está tentando engadir algo nunha cola, no caso encantador que a cabeza pasa para estar aquí, é moi doado para nós só para ir ata o final introducir algo, non? Pero o punto enteiro dunha fila é que a cabeza pode realmente dinamicamente cambiar, dependendo de onde nós quere o inicio da nosa q ser, e, como tal, a cola tamén vai cambiar. E así imaxinar que este non era o cola, pero esta foi a cola. Imos dicir que a cabeza está ben aquí. Imos dicir que a nosa cola mirou como esta. Se quixésemos desprazarse onde o inicio da liña é, imos dicir que cambiou cabeza Deste xeito e tamaños aquí. Agora queremos engadir algo ao esa cola, pero como podedes ver, non é tan sinxelo como só engadir o que é despois do tamaño porque entón nós funcionan fóra do límites da nosa matriz real. Onde queremos realmente é here. Esa é a beleza dunha fila é que, para nós, visualmente Parece que a liña vai como esta, pero cando gardada nunha estrutura de datos, eles dan-lo como como un ciclo. É o tipo de implica á fronte do mesmo xeito que unha liña tamén pode envolve en torno dependendo de onde queira que quere inicio da liña para ser. E por iso, se derme un mirar para abaixo aquí, imos dicir que quería crear un función chamada enqueue. Queriamos engadir int n en que q. Se q.size nós q-- chamaremos que os nosos datos structure-- o noso queue.size non igual capacidade ou é menos que a capacidade, q.strings é a matriz dentro da nosa q. Estamos indo para definir que igual a q.heads, que é aquí, ademais de q.size módulo pola capacidade que envolve-nos de volta por aquí. Así, neste exemplo, o índice de de cabeza é un, non? O índice de tamaño é 0, 1, 2, 3, 4. Entón, podemos facer un módulo 4 pola nosa capacidade, que é 5. O que isto nos dá? Que o índice sae desta? Audiencia: 0. ANDI Pengo: 0, que pasa a ser aquí, e por iso queremos ser capaces para introducir aquí. E así esta ecuación tipo aquí de só funciona con todos os números dependendo de que o seu cabeza eo seu tamaño é. Se sabe o que os as cousas son, vostede sabe exactamente onde quere inserir todo o que é despois da súa cola. Isto ten sentido para todos? Eu sei que tipo de un cerebro provocación especialmente xa que este veu tras o seu quiz. Pero espero que todos agora pode entender por iso que esta solución ou este función é a forma que é. Calquera algo incerto sobre iso? Aceptar. E agora, se quería para retirar da cola, este é onde a nosa cabeza sería desprazando porque se fósemos para retirar da cola, nós non aproveitar a fin de q. Queremos aproveitar a cabeza, non? Entón, como resultado, a cabeza vai cambiar, e é por iso que cando enfileirar, ten que manter o control de onde a súa cabeza eo seu tamaño son para poder introducir para a posición correcta. E así, cando retirar da cola, Eu tamén Pseudocódigo-lo. Sinto-se libre para se quere o intento de codificación iso. Quere mover a cabeza, non? Se eu quixese para retirar da cola, eu movería a cabeza sobre. Esta sería a cabeza. E o noso tamaño actual faría restar porque xa non temos catro elementos na matriz. Nós só temos tres, e entón nós queremos para voltar o que estaba almacenado dentro da cabeza porque queremos aproveitar esta valor para fóra de modo moi similar ao do conxunto. Así está tomando dun lugar distinto, e ten que volver a asignar o punteiro a lugar diferente como resultado. Loxicamente, todos sigan? Gran. OK, entón imos falar un pouco máis en profundidade sobre listas ligadas que vai ser moi, moi valioso para que no transcurso desta semana Serie de exercicios. Listas ligadas, como vostedes lembro, todos eles son son os nós que son nós de certa valores de ambos un valor e un punteiro que están ligados entre si por eses punteiros. E así, a estrutura de como creamos un nó aquí é nós ten int n, que é o que quere o valor nunha tenda ou cadea de n ou o que sexa chama-lo, o carácter estrela n. Struct estrela no, que é o punteiro que quere ter en cada nodo, vai ter que punteiro punto cara ao lado. Vai ter a cabeza dunha lista ligada que está indo para ligar para o resto os valores así por diante e así por diante ata que finalmente chegar ao final. E esta última nodo é só indo para non ter un punteiro. Vai apuntar null, e que, cando sabe que bateu o final da lista ligada é cando o último punteiro non apunta a algo. Entón, nós estamos indo a ir un pouco máis en profundidade acerca de como se faría posiblemente buscar unha lista ligada. Teña en conta que o que son algúns dos inconvenientes das listas ligadas versículos unha matriz sobre investigacións. Unha matriz que poida busca binaria, pero por que non pode facer iso nunha lista vinculada? Audiencia: Porque están todos conectados, pero non sei ben onde [Inaudível]. ANDI Pengo: Si, exactamente por iso Lembre que o brillo dunha matriz foi o feito de que tiñamos memoria de acceso aleatorio onde se eu quería o valor do índice seis, eu podería só dicir índice seis, dáme ese valor. E iso é porque as matrices son clasificadas nun espazo contiguo de memoria nun só lugar, mentres que tipo de listas ligadas son intercaladas aleatoriamente por todas partes, ea única forma que pode atopar un é a través dun punteiro que lle di a dirección de onde a seguinte nodo é. E así, como resultado, o único xeito para buscar unha lista ligada é a procura lineal. Porque eu non sei exactamente onde o valor 12º na lista ligada é, Teño que atravesar a totalidade desa lista un conectado a un, da cabeza para o primeiro nodo, para o segundo no, para o terceiro no, todo o camiño ata que finalmente chegar onde este nodo eu estou buscando é. E así, neste sentido, busca nunha lista ligada sempre n. Sempre n. Sempre en tempo lineal. E así o código en que imos aplicar isto, e isto é un pouco novo para vostedes sempre que caras realmente non teño falado ou nunca punteiros visto en como buscar a través de punteiros, entón imos percorrer esta moi, moi lentamente. Así, busca bool, dereito, imos imaxinar que queremos para crear unha función chamada investigación que retorna certo Se atopou un valor dentro do ligada lista, e retorna false doutra forma. Lista estrela nodo é Actualmente só o punteiro para o primeiro elemento na súa lista ligada. int n é o valor que está buscando na lista. Entón punteiro estrela nó lista é igual. Isto significa que estamos establecendo e creando un punteiro para que o primeiro nodo dentro da lista. Todos comigo? Entón, se tivésemos que ir volver aquí, eu tería iniciar un punteiro que indica o cabeza de todo o que é lista. E, a continuación, unha vez que chegar aquí, mentres punteiro non é igual a null, de xeito que é o ciclo no que estamos será, subsecuentemente, atravesando resto da nosa lista, xa que o que ocorre cando o punteiro é igual a null? Sabemos que have-- Audiencia: [inaudível] ANDI Pengo: Exactamente, polo que sabemos que chegamos ao final da lista, non? Se volver aquí, cada nodo debe estar apuntando a outro nodo e así por diante e así por diante ata chegar finalmente a cola da lista ligada, que ten un punteiro que non apunta calquera lugar que non. E para que vostede sabe que, basicamente, súa lista aínda está alí enriba ata punteiro non é igual nula porque unha vez que é igual a null, vostede sabe que non hai máis cousas. Entón ese é o ciclo no que estamos terá a investigación real. E se os pointer-- ve este tipo de función frecha alí? Polo tanto, se o punteiro apunta n, se o punteiro na que n é igual é igual a N, de modo que significa que se o punteiro que é buscando no extremo de cada nodo é efectivamente igual ao valor está a buscar, a continuación, quere voltar certo. Entón, basicamente, se está en un nó que ten o valor que está a buscar, vostede sabe que estivo capaz de investigación con éxito. Se non, quere establecer o punteiro ao seguinte nodo. Iso é o que esta liña está facendo aquí. Punteiro é igual punteiro próximo. Todo o mundo ver como é que está a traballar? E, esencialmente, vai só atravesan a totalidade da lista, axustar o punteiro á vez ata finalmente bateu o final da lista. E vostede sabe que non hai máis nós para buscar, e entón pode volver false porque sabe que, oh, así, se eu fun capaz de buscar a través da totalidade da lista. Neste exemplo, se eu quixese a ollar para o valor de 10, e eu comezo na cabeza, e Eu busco todo o camiño, e finalmente cheguei a esta, que un punteiro que apunta a null, Sei que, un porco, eu creo que 10 non está en esta lista porque eu non podería atopalo. E eu estou no final da lista. E no caso de que vostede sabe Eu estou indo a voltar falso. Deixe que salsa en algo. Isto vai ser moi importante para o seu pset. A lóxica del é moi sinxelo, quizais sintaticamente só implementar lo. Vós queredes facer Asegúrese de que entenda. Legal. OK, entón como nós ficaríamos inserción de nós, seguro, nunha lista de lembrar, porque o que son o que os beneficios de ter unha lista vinculada contra unha matriz en termos de almacenamento? Audiencia: É dinámico, polo que é máis fácil a-- ANDI Pengo: Exactamente, polo que é dinámica, o que significa que pode expandir-se e encoller dependendo das necesidades do usuario. E así, neste sentido, non precisamos perder memoria innecesaria porque se eu non sei cantos valores que quero a tenda, non ten sentido para min para crear unha matriz porque se eu queira gardar 10 valores e eu crear unha matriz de 1000, que é unha gran cantidade de memoria desperdiçada, asignado. É por iso que queremos usar un conectado lista para poder dinamicamente cambiar ou diminuír o tamaño da nosa. E así que fai a inserción un pouco máis complicado. Xa que non podemos acceder ao azar elementos do xeito que queremos unha matriz. Se eu queira inserir un elemento na sétima índice, Só pode inserir-lo na sétima índice. Nunha lista ligada, iso non acontece bastante traballar tan facilmente, e polo que se queriamos para introducir aquí na lista ligada, visualmente, é moi fácil de ver. Nós só queremos inserir-lo alí mesmo, ao comezo da lista, logo da cabeza. Pero o xeito no que temos que volver asignar os punteiros é un pouco complicado ou, loxicamente, ten sentido, pero quere estar seguro de que ten- completamente abaixo, porque a última cousa que quere é reatribuído un punteiro a xeito que nós estamos facendo aquí. Se eliminar a referencia ao punteiro da cabeza aos 1, entón, de súpeto, o resto da súa lista ligada está perdido, porque non ten, en realidade, creado un nada temporal. Isto sinalou o 2. Se trasladar o punteiro, entón o resto da súa lista está totalmente perdido. Entón quere ser moi, moi coidado aquí para asignar o primeiro punteiro de todo o que quere inserir en calquera lugar quere, e entón pode cancelar o resto da súa lista. Entón, iso é aplicable a onde quere estás inserir. Se desexa inserir no cabeza, se quere responder aquí, se quere inserir no Ao final, así, a fin I creo que faría só Non ten un punteiro, pero Quere ter a certeza de que non facer perder o resto da súa lista. Sempre quere estar seguro o novo nó está apuntando no sentido de todo o que quere introducir, e entón pode engadir o fío diante. Todo o mundo é clara? Este será unha das cuestións reais. Unha das máis importantes cuestións terá no seu pset é que está indo a tentar crear unha lista encadeada e as cousas de inserción pero despois é só perder o resto da súa lista ligada. E vai ser como eu Non sei por que isto está a suceder? E é unha dor de pasar por e buscar todos os seus punteiros. E eu asegura que nesta pset, escribir e debuxar eses nós fóra vai ser moi, moi útil. Para que poida manter completamente a noción de onde os seus punteiros son, o que está a suceder de malo, onde todos os seus nodos son, o que cómpre facer para acceder ou inserir ou eliminar ou ningún deles. Todos ben con iso? Legal. Entón, se nós quería mirar o código? Oh, eu non sei se nós pode ver as-- OK, entón na parte superior de todo, é unha función inserción nomeado onde queremos para inserir int n na lista ligada. Nós imos camiñar por este. É unha morea de código, unha morea de nova sintaxe. Nós imos estar ben. Así, na parte superior, sempre que queremos crear nada o que necesitamos facer, especialmente se quere que non debe ser almacenado na pila pero na pila? Nós imos para un malloc, non? Entón imos crear un punteiro. No, punteiro, novas equals malloc o tamaño dun nodo porque queremos que nó a crear. Queremos que a cantidade de memoria que un nó ocupa sendo asignado ao creación do novo nó. E entón nós imos comprobar a ver se é igual a novos iguais nulo. Teña en conta que do que dixemos? Todo o que malloc, o que ten que sempre facer? Ten que sempre comprobar a ver se iso é ou non nulo. Por exemplo, se o seu funcionamento sistema foi completamente cheo, se non tiña máis memoria todo e intentar malloc, ía voltar nulo para ti. E por iso, se tentar usalo cando estaba a apuntar cara null, non vai poder para acceder a esta información. E así, como tal, nós queriamos facer Asegúrese de que sempre que está mallocing, está sempre comprobando se que a memoria dado a ti é nulo. E se non é, entón podemos pasar co resto do noso código. Entón, nós estamos indo a iniciar o novo nó. Nós imos facer nova n é igual a n. E entón nós imos facer definir novo o punteiro na nova como nulo porque agora non quere nada para el para apuntar. Nós non temos ningunha idea de onde vai poñer-lo, e, a continuación, se queremos inserir-lo na cabeza, entón podemos asignar novo o punteiro para a cabeza. Será que todo o mundo seguir a lóxica de onde isto está a suceder? Todo o que estamos facendo é crear unha nova no, establecer o punteiro para null, e, a continuación, a reasignación Lo á cabeza se sabemos que queremos para inserir-lo na cabeza. E, a continuación, a cabeza vai apuntan que o novo nó. Todos ben con iso? Polo tanto, é un proceso de dúas etapas. Ten que primeiro asignar o que quere que está creando. Establecer que punteiro para o referencia, e entón pode tipo de dereference o primeiro punteiro e sinala-lo para o novo nó. Onde queira que quere inserir-lo, que a lóxica vai realizar certo. É unha especie de como asignar variables temporais. Lembre, ten para asegurarse de que non perder de vista que está cambiando. Quere estar seguro de que vostede ten un variable temporal este tipo de garda o control de onde esa cousa se garda para que non perden calquera valor no curso de como xogar con el. OK, entón o código será aquí. Vostedes vexan despois da sección. Vai estar alí. Entón eu creo que como é que iso difire se quixésemos introducir no medio ou no fin? Alguén ten unha idea de cal é o pseudocódigo como referencia lóxica que levaría se quixésemos para inserir-lo no medio? Entón, se nós quería para inserir-lo no cabeza, todo o que facemos é crear un novo nodo. Nós axustar o punteiro do que novo nodo a todo o que a cabeza, e, a continuación, imos definir o cabeza ao novo nodo, non? Se quixésemos para inserir-lo no medio da lista, o que tería que facer? Audiencia: É aínda faría ser un proceso semellante de como a asignación de punteiro e a continuación, atribuíndo este punteiro, pero teriamos que atopar alí. ANDI Pengo: Exactamente, exactamente por iso o mesmo proceso, agás que ten que atopar onde exactamente quere que o novo punteiro para entrar, por iso, se quero introducir en no medio ligado lista-- OK, imos dicir que esa é a nosa lista ligada. Se queremos inserir-lo aquí, imos crear unha nova no. Estamos indo para malloc. Nós imos crear unha nova no. Nós imos asignar o punteiro deste nodo aquí. Pero o problema que difire de onde a cabeza é é que nós sabiamos exactamente onde está a cabeza. Foi á dereita na primeira, non? Pero aquí temos que manter o control de onde estamos introducindo-o. Se estamos introducindo noso nó aquí, temos para asegurarse de que o anterior a este nodo é aquel que atribúe novo o punteiro. Entón tes que tipo de manter o control de dúas cousas. Se manter o control de onde esta nó actualmente está inserindo. Tamén ten que manter o control de onde o no anterior que está mirando tamén estaba alí. Todos ben con iso? Aceptar. Como case introducir ao final? Se eu quería engadir lo aqui-- se eu quería para engadir un novo nodo ao final dunha lista, como eu podería ir sobre como facelo? Audiencia: Entón, actualmente, a do último apuntado como nulo. ANDI Pengo: Si. Exactamente, polo que este Actualmente é apuntado saber, e entón eu creo que, nese sentido, é moi fácil de engadir ao final dunha lista. Todo o que tes que facer é configurar-lo igual a nulo e despois crecer. Ben alí, moi fácil. Moi sinxelo. Moi semellante ao cabeza, pero loxicamente vostede quere estar seguro de que os pasos tomar para facer nada diso, está acompañando. É moi fácil, no medio do seu código, collo, Oh, eu teño tantos punteiros. Non sei onde nada está a apuntar. Eu non sei cal o nodo no que estou. Qué está a pasar? Relax, calme-se, tomar unha respiración profunda. Debuxe a súa lista ligada. Se digo, eu sei onde exactamente Necesito inserir isto en e sei exactamente como recolocar o meu punteiros, moito, moito máis fácil de imaxinar out-- moito máis fácil de non perderse nos erros do seu código. Todos ben con iso? Aceptar. Entón eu creo que un concepto que non ten realmente falamos antes agora, e eu creo que probablemente Non vai atopar moi yet-- é unha especie de un concept-- avanzada é que realmente temos un conxunto de datos estrutura chamada unha lista dobremente ligada. Entón, como podedes ver, todo o que estamos facendo é crear un valor real, un extra punteiro en cada unha das nosas nós que tamén apunta para o nodo anterior. Polo tanto, non só temos o noso nós apuntar á seguinte. Eles apuntan ao anterior. Vou ignorar estas dúas agora. Entón tes unha cadea que pode moverse en ambos os sentidos, e entón é un pouco máis fácil a continuación loxicamente xunto. Como aquí, en vez de manter o control de, oh, I Ten que saber que este nodo é o que eu teño que volver a asignar, Só podo ir aquí e basta tirar o anterior. Entón eu sei exactamente onde que é, e entón Non ten que atravesar a totalidade da lista ligada. É un pouco máis fácil. Pero, como tal, ten dobremente a cantidade de punteiros, que é o dobre da cantidade de memoria. É unha morea de agullas para acompañar. É un pouco máis complexo, pero é un pouco máis agradable, dependendo o que estás a realizar. Polo tanto, este tipo de datos estrutura existe totalmente, ea estrutura para é moi, moi simple, excepto todo o que está a ter é, no canto de só un punteiro para o próximo, tamén ten un punteiro para anterior. Isto é todo o que a diferenza era. Todos ben con iso? Legal. Todo ben, entón agora eu son para realmente pasar seguramente como 15 a 20 minutos ou a granel do resto do tempo na sección falando de táboas de hash. Como moitos de vostedes lin pset5 especificación? Todo ben, bo. Iso é máis elevado que o 50% do normal. Está ben. Entón, como vostedes van ver, es desafío en pset5 será a posta en marcha dun dicionario onde cargar máis de 140.000 palabras que nós dámoslle e corrector ortográfico contra todo o texto. Nós imos darlle aleatoria pezas de literatura. Nós imos darlle o Odyssey. Nós imos dar-lle a Ilíada. Nós imos darlle Austin Powers. E o seu desafío será a de corrector ortográfico cada palabra en todo destes dicionarios esencialmente co noso corrector ortográfico. E por iso hai poucas partes de crear este pset, primeiro quere ser capaz de cargar, de feito, todas as palabras no seu dicionario, e entón Quere ser capaz de corrector ortográfico todos eles. E así, como tal, está indo para esixir unha estrutura de datos que pode facelo rápido e eficiente e de forma dinámica. Entón, eu supoño que o máis fácil xeito de facelo, probablemente crear unha matriz, non? O xeito máis doado de almacenamento é vostede Pode crear unha matriz de 140.000 palabras e só poñer-los todos alí e entón atravesala los por busca binaria ou polas seleccións ou não-- Lamentamos que é a clasificación. Pode clasificalos los e despois atravesa-los por busca binaria ou busca só lineal e só as palabras finais, pero que leva unha gran cantidade de memoria, e non é moi eficiente. E así imos comezar fala de formas de facer noso tempo de funcionamento máis eficiente. E o noso obxectivo é facer que constante de tempo onde é case como matrices, onde ten acceso instantáneo. Se eu quixese buscar calquera cousa, Quero ser capaz de só, crecemento, atopalo exactamente, e puxe-o para fora. E así unha estrutura na que nós imos estar a facer-se moi preto para acceder a constante tempo, ese Santo Graal na programación da constante tempo chámase táboa de hash. E así por David mencionado anteriormente o [Inaudível] un pouco na charla, pero nós imos realmente mergullo en profundidade esta semana nun anaco que está sobre como unha táboa hash funciona. Así, a forma que un hash obras de mesa, por exemplo, se eu quería gardar un monte de palabras, un chea de palabras no idioma inglés, Eu podería, en teoría, poñer bananas, mazá, kiwi, mango, par, e melón todo en só unha matriz. Todos eles poderían encaixar e ser atopar. Sería unha especie de dor para buscar e acceso, pero o xeito máis doado de facelo é que pode crear efectivamente unha estrutura chamado unha táboa hash onde nós hash. Corremos todos os nosos chaves través unha función hash, unha ecuación, que transforma-los todos algún tipo de valor que entón podemos almacenar en esencialmente un array de lista ligada. E aquí, se quixésemos para almacenar palabras en inglés, Podemos potencialmente só, eu non sabe, transformar as primeiras letras en algún tipo de un número. E así, por exemplo, se eu quixese Un a ser sinónimo de apple-- ou co índice de 0, e B sendo sinónimo de 1, podemos ter 26 entradas que poden só almacenar todas as letras do alfabeto que imos comezar. E entón podemos ter mazá no índice de 0. Podemos ter de bananas no índice de 1, melón no índice de 2, e así por diante e así por diante. E, así, se eu quixese buscar meu hash de mesa e acceso mazá, Sei que Apple comeza con un A, e sei exactamente que debe ser eo hash táboa no índice 0, pois da función asignado anteriormente. Entón, eu non sei, somos un programa de usuario, onde vai ser cobra con non arbitrarily-- arbitrariamente, coa tentativa de pensativamente pensar en boas ecuacións para poder estenderse fóra todos os seus valores dun xeito que poden acceder facilmente Lo máis tarde con como unha ecuación que, vostede mesmo, sabe. Así, no sentido de que eu quería ir a manga, sei, oh, el comeza con m. Debe ser no índice de 12. Non teño a busca a través de calquera cousa. Sei exactly-- eu podería só ir o índice de 12 e tirar iso. Todos clara sobre como un A función da táboa hash funciona? É unha especie de só unha matriz máis complexa. Isto é todo o que é. Aceptar. Entón eu creo que correr en esta cuestión que acontece se ten moitas cousas que darlle o mesmo índice? Entón, dicir que a nosa función, o único que fixo foi tomar esta primeira letra e transformar isto nun respectivo contido 0 a 25. Isto é totalmente ben se só ten un de cada. Pero a segunda comeza ter máis, é terá o que se chama unha colisión. Entón, se eu tentar inserir enterrar nun hash táboa que xa bananas nel, o que vai pasar cando tentar inserir iso? Cousas malas debido á banana Xa existe dentro do índice que quere almacena-lo. Berry tipo de é como, ah, o que fago? Non sei onde ir. Como podo solucionar isto? E así vostedes van tipo de ver o que facemos esta cousa complicada onde podemos tipo de verdade crear lista ligada nas nosas matrices. E así, o xeito máis doado para pensar sobre iso, todo é unha táboa hash matriz de listas ligadas. E así, neste sentido, ten esta fermosa matriz de punteiros, e, a continuación, en cada punteiro este valor, no que o índice, realmente apuntar para outras cousas. E entón tes todos eses separado cadeas saíndo dunha gran matriz. E aquí, se eu quería introducir baga, Sei, OK, eu estou indo a introducir Lo través da miña función hash. Vou acabar co índice de 1, e entón eu vou ser capaz de ter só un subconxunto menor desta xigante dicionario de 140.000 palabras. E entón eu podo só ollar mediante 1/26 do que iso. E entón eu só podo inserir baga, tanto antes ou despois da banana neste caso? Despois, non? E entón vai querer inserir ese nó despois de bananas, e entón vai para introducir en que a cola de lista ligada. Vou volver a este slide anterior, para que vostedes poidan ver como función hash funciona. Entón función hash é esta ecuación que está executando o seu tipo de entrada través de obter o que quere índice desexa asignar-lo para. E así, neste exemplo, todo o que queriamos a facer era tomar a primeira letra, transformar isto nun índice, entón nós pode almacenar que na nosa función hash. Todo o que estamos facendo aquí é que estamos converter a primeira letra. Entón KeyKey [0] é só a primeira letra de calquera secuencia que estamos tendo, estamos pasando. Estamos convertendo que a superior, e estamos subtraindo por letras maiúsculas A, así todo o que está facendo está nos dando un número no que podemos botar nosos valores para. E entón nós imos voltar de hash TAMAÑO módulo. Sexa moito, moito coidado porque, en teoría, aquí o seu valor de hash pode ser infinita. El podería simplemente ir sobre e sobre e sobre. Pode haber algunha verdade, realmente grande valor, senón porque a súa táboa hash que que creou posúe só 26 índices, quere estar seguro do seu modulusing para que non run-- é o mesmo cousa como o seu queue-- para que non corra fóra da inferior da súa función hash. Quere envolve-la de volta de todo do mesmo xeito en [inaudível] cando tivo como un moito, moi grande carta, vostede Non quería que isto basta realizar fóra da final. Mesmo aquí, quere asegurarse de non se executa fóra da final por implicación en torno ao principio da mesa. Polo tanto, esta é só unha moi función hash simple. Todo o que fixen foi dar o primeiro carta de todo o que o noso contribución foi e transformar isto nun índice que poderiamos poñer na nosa táboa de hash. Si, e así como dixen antes, a forma que nós resolver colisións na nosa hash de táboas están tendo, o que chamamos fío. Entón, se tentar inserir múltiple palabras que comezan con o mesmo, terá un valor de hash. Aguacate e mazá, se ten executa-lo a través da nosa función hash, vai darlle a mesmo número, o número de 0. E así a nosa forma de solucionar isto é que podemos realmente tipo de vincula-los xuntos vía listas ligadas. E así, neste sentido, podedes ver especie de forma que as estruturas de datos vimos creación anteriormente como unha uva pasa ligada lista especie de poden unirse nun só. E entón podes crear moito estruturas de datos máis eficientes que pode tratar con grandes cantidades de datos, que redimensionar dinamicamente dependendo das súas necesidades. Todo o mundo é clara? Todos tipo de clara sobre o que pasa aquí? Se eu quixese insert-- o que é un froita que comeza con, eu non sei, B, con excepción baga, bananas. Audiencia: Blackberry. ANDI Pengo: Blackberry, amor. Onde é que blackberry aquí? Ben, nós realmente non resolver iso aínda, pero, en teoría, se quixésemos ter este por orde alfabética, onde debe ir blackberry? Audiencia: [inaudível] ANDI Pengo: Exactamente, tras aquí, non? Pero xa que é moi difícil reorder-- Coido que cómpre a vostedes. Podedes totalmente aplicar o que quere. O xeito máis eficaz de facelo, quizais, sería a de clasificar a súa conectado lista en orde alfabética, e entón cando está inserción de cousas, quere estar seguro de inserir-los en orde alfabética para que, a continuación, cando está intentando buscalos, non ten que atravesar todo. Vostede sabe exactamente onde que é, e é máis fácil. Pero se tipo de cousas intercalado azar, aínda vai ter para cruzalo de calquera maneira. E entón se eu quería só inserir blackberry aquí e eu quería buscar iso, eu sei, ah, blackberry debe comezar co índice de 1, entón eu saber instantáneamente pode buscar a 1. E entón eu podo tipo de atravesar a lista vinculada ata chegar ao BlackBerry, e entăo-- si? Audiencia: Se estás a create-- Creo que como este é un hash moi sinxelo función. E se o que queriamos facer varias capas de que, como o OK, queremos separar en como todas as letras do alfabeto e logo de novo a gustar doutro conxunto de letras do alfabeto en que, que estamos poñendo como un hash táboa dentro dunha táboa hash, ou como unha función dentro dunha función? Ou é isso-- ANDI Pengo: Entón seu haxix function-- súa táboa hash pode ser tan grande como queres que. Polo tanto, neste sentido, penso era moi fácil, moi simple para min en base só sorte en cartas de primeira palabra. E por iso hai só 26 opcións. Só pode obter 26 opcións de 0-25 porque só poden comezar da a Z. Pero Se quería que engadir, quizais, máis complexidade ou máis rápido tempo de execución para o seu táboa de hash, é absolutamente pode facer todo tipo de cousas. Podes facer o seu propio ecuación que dá a vostede máis na súa distribución palabras, entón cando procura, que vai ser máis rápido. É totalmente ata vós como quere aplicar iso. Pense nisso como só baldes. Se eu quería ter 26 baldes, eu vou para resolver as cousas para os baldes. Pero eu vou ter unha chea de material en cada balde, por iso, se quere facelo máis rápido e máis eficiente, déixeme ter cen baldes. Pero entón tes que descubrir unha forma de resolver as cousas para que sexan no balde adecuada deben estar en. Pero entón cando realmente quero ver ese balde, é moito máis rápido porque non hai menos cousas en cada balde. E entón, si, iso é verdade, o truco para vós en pset5 é que vai ser reto a crear só calquera que sexa o máis eficiente función que pode pensar de ser capaz de almacenar e comprobar eses valores. Totalmente ata vós con todo, quere facelo, pero iso é un punto moi bo. Que tipo de lóxica que quere comezar a pensar en é, así, por que non podo facer máis baldes. E entón eu teño que buscar menos cousas, e entón quizais eu ten unha función hash diferente. Si, hai unha morea de formas de facelo pset, algúns son máis rápidos que outros. Estou totalmente vai só ver como rápido foi o máis rápido que vostedes van poder obter as súas funcións para traballar. OK, todo en bo fío e hash táboas? É realmente como unha forma moi simple concepto, se pensar sobre iso. Todo o que é separar o que quere súas entradas están en baldes, clasificándose os, a continuación, buscar o lista que non está asociado. Legal. Todo ben, agora temos un tipo de estrutura de datos que se chama unha árbore. Imos seguir adiante e falar intentos que son distintas diferentes, pero na mesma categoría. Esencialmente, toda a árbore é xa de organización de datos en forma lineal que unha táboa hash does-- vostede sabe, ten un superior e un inferior e, a continuación, tipo de conexión fóra dun ele-- árbore ten un top que chamar a raíz, e logo, ten as follas toda en torno a el. E así todo o que tes aquí é só o nodo superior que apunta a outros nós, que puntos para máis nós, e así por diante e así por diante. E así só ten ramas de división. É só un xeito diferente de organizar datos, e porque o chamamos dunha árbore, vostedes só-- é só modelado para parecerse a unha árbore. É por iso que nós o chamamos árbores. Táboa de hash parece unha táboa. Unha árbore só parece unha árbore. Todo o que é un separado forma de organizar os nós dependendo de cales son as súas necesidades. Entón tes unha raíz e entón tes follas. O xeito que podemos particularmente pensar sobre iso é unha árbore binaria, unha árbore binaria é só un tipo específico dunha árbore onde cada nodo únicos puntos a, como máximo, dous outros nós. E por iso aquí tes distintas simetría na súa árbore que fará máis tipo de ollar en que os valores que son, porque entón ter sempre un esquerdo ou dereito. Nunca hai como unha terceira esquerda de á esquerda ou un cuarto da esquerda. É só ten unha esquerda e unha dereita e pode buscar calquera dos dous. E así por que isto é útil? O xeito que se trata é útil se está a buscar a procura a través de valores, non? No canto de aplicar binario buscar nunha matriz de erro, se quería ser capaz de inserir os nós e aproveitar os nós a gusto e tamén preservar a busca capacidades de procura binaria. Así, deste xeito, somos tipo de tricking-- lembro cando dixo listas ligadas non podo busca binaria? Estamos tipo de creación dunha estrutura de datos que trucos que traballar. E iso porque listas ligadas son lineais, eles só conectar un despois do outro. Podemos tipo de distinto tipo de punteiros que ligan con diferentes nós que pode axudarnos coa investigación. E aquí, se eu quixese ter unha árbore de busca binaria, Sei que o meu medio se 55. Eu só vou crear este como o meu medio, como a miña raíz, e entón eu vou ter valores xirar fóra del. Entón, aquí, se eu vou buscar o valor de 66, podo comezar a 55. É 66 maior que 55? Si, é, entón eu sei que mus investigación i n o punteiro dereita da árbore. Eu vou a 77. OK, é menos que 66 ou maior que 77? É menos que, por iso, vostede sabe, oh, que ten que ser o no da esquerda. E entón aquí estamos tipo de preservación todas as grandes cousas sobre arrays, así como redimensionamento dinámico de obxectos, sendo capaz de inserir e eliminar a gusto, sen ter que se preocupar co fixo cantidade de espazo. Aínda preservar todos aquelas cousas marabillosas mentres tamén é capaz de conservar a rexistro e tempo de procura binaria investigación que só anteriormente capaz de obter unha frase. Estrutura de datos legal, tipo de complexo de implementar, o no. Como verás, todo o que representa a estrutura do nodo é que ten unha esquerda e un punteiro dereito. Isto é todo o que é. Entón, en vez de só Tendo un X ou unha anterior. Ten unha esquerda ou á dereita, e, a continuación, pode tipo de liga-los xuntos con todo escolle así. OK, imos realmente basta sacar algúns minutos. Entón imos voltar aquí. Como dixen anteriormente, Eu medio que explicou a lóxica por tras de como nós ía buscar por iso. Estamos indo para tratar de pseudocoding este para fóra para ver se podemos aplicar o tipo de mesma lóxica de busca binaria a un tipo de estrutura de datos. Se vós queredes tomar como unha parella minutos para só pensar sobre iso. Aceptar. Todo ben, eu vou en realidade, só darlle as-- non, imos falar do pseudocódigo primeiro. Entón, alguén quere para dar unha facada en que o primeiro que quere facer cando está empezando a procura? Se estamos a buscar o valor de 66, o que é o primeiro que queremos facer, se queremos Busca binaria esta árbore? Audiencia: Quere ollar dereito e mirar esquerda para ver [inaudível] maior número. ANDI Pengo: Si, exactamente. Entón, vai mirar para a súa raíz. Hai moitas formas que pode chamar el, o seu nó pai persoas din. Eu gusto de dicir porque raíz que é como a raíz da árbore. Vai mirar para o no raíz, e está vai ver é 66 maior que é menor que 55. E se é maior que, así, é superior, onde é que imos querer ollar? Onde queremos buscar agora, non? Queremos buscar o metade dereita da árbore. Polo tanto, temos, convenientemente, un punteiro que apunta cara á dereita. E entón podemos definir nosa nova raíz para ser 77. Podemos só ir onde queira o punteiro está apuntando. Ben, oh, aquí estamos empezando aos 77 anos, e podemos só facelo de forma recursiva novo e de novo. Deste xeito, medio de ter unha función. Ten unha forma de buscar que pode só repetir máis e máis e máis, dependendo de onde quere ollar ata finalmente chegar ao valor que está a procurar. Ten sentido? Estou a piques de amosar-lle o real código, e é unha morea de código. Non é necesario asustar. Imos falar con el. En realidade, non. Isto foi só pseudocódigo. OK, iso foi só o pseudocódigo, que é un pouco complexo, pero é totalmente bo. Todos seguindo ao longo aquí? Se a raíz é nulo, o retorno falso, porque iso significa non ten sequera algo alí. Se raíz n é o valor, polo que se pasa a ser o que está mirando, entón está indo para volver true porque sabe que atopou. Pero, se o valor é inferior de raíz n, es vai buscar á esquerda neno ou a folla esquerda, todo o que sexa chamalo. E se o valor é superior a raíz, está indo a buscar a árbore dereita, a continuación, pode realizar a función a través de busca de novo. E se a raíz é nulo, para que aquel Significa que chegou ao fin? Isto significa que non ten ningunha máis máis follas de investigación, entón vostede sabe, oh, I creo que non é aquí porque despois de que eu olhei través a cousa toda e non é aquí, el só podería non estar aquí. Isto ten sentido para todos? Entón, é como busca binaria preservación as capacidades de listas ligadas. Arrefecer, e de xeito que o segundo tipo de estrutura de datos que vostedes pode tentar implementar no seu pset, só tes que escoller un método. Pero quizais un método alternativo para a táboa hash é o que chamamos un trie. Todo é un trie é un tipo específico de árbore que ten valores que van a outros valores. Entón, en vez de ter un par árbore no sentido de que un cousa pode ligar a dous, pode que unha cousa apunte a moitas, moitas cousas. Ten basicamente matrices dentro do cal almacena punteiros que ligan con outras matrices. Así, o no de como nós definiría un trie é que queremos ter un Booleano, palabra c, non? Así, o nodo é booleano como verdadeira ou falsa, en primeiro lugar, por diante de esa matriz, iso é unha palabra? En segundo lugar, quere ter punteiros a todo o que o resto deles son. Un pouco complexo, un pouco abstracto, mais Vou explicar o que todo isto significa. Entón, aquí, na parte superior, se teño unha matriz xa declarou, un nó no que ten un valor booleano valor almacenado diante que lle di é esta unha palabra? Non é esta unha palabra? E entón tes o resto da súa matriz que de feito, almacena todas as posibilidades do que podería ser. Así, por exemplo, como na parte superior ten o primeiro que di certa ou falso, si ou non, esta é unha palabra. E entón tes de 0 a 26 as cartas que pode almacenar. Se eu quixese buscar aquí para morcego, eu ir para arriba e eu ollo para B. Creo B na miña array, e entón eu sei, OK, é unha palabra B? B non é unha palabra, así que así Debo seguir buscando. Vou de B, e eu ollo para o punteiro que apunta a B e vexo outro conxunto de información, a mesma estrutura que tiñamos antes. E aqui-- oh, o seguinte carta en [inaudível] é A. Entón, nós miramos nese array. Atopamos o oitavo valor, e, despois, ollar para ver, oh, hey, que é unha palabra, é B-A unha palabra? Non é unha palabra. Temos que seguir buscando. E entón miramos para onde o punteiro de puntos A, e apunta a outra forma en que temos máis valor almacenado. E, finalmente, hai que B-A-T, o que é unha palabra. E así a próxima vez mira, está indo para ter ese cheque de si, esta función booleana é certa. E así, no sentido de que estamos especie de ter unha árbore con matrices. Entón podes tipo de busca para abaixo. En vez de unha función hash e atribuíndo valores de lista ligada, pode simplemente aplicar un trie que busca downwords. Realmente, realmente complicado cousas. Non é doado pensar, porque son como cuspindo tantas estruturas de datos para fóra en ti, pero como todo tipo de entender como a lóxica de todo isto funciona? OK, legal. Así B-A-T e logo vai buscar. A próxima vez que está indo para ver, oh, hey, é certo, así, sei que isto debe ser unha palabra. Mesmo para xardín zoolóxico. Entón aquí é o correcto agora, se nós quería buscar zoo, agora, Actualmente non é un xardín zoolóxico palabra na nosa dicionario porque, como podedes ver, o o primeiro que temos un booleano return true é a finais de zoom. Temos Z-O-O-H. E aquí, non realmente ter a palabra, zoo, no noso dicionario porque esta caixa de verificación non está marcada. Así, o ordenador non fai sei que zoo é unha palabra porque a forma que temos almacenados, só un zoom aquí de feito ten un valor booleano que foi virou verdade. Polo tanto, se queremos introducir o palabra, zoo, no noso dicionario, como é que imos facer sobre iso? O que temos que facer para garantir que a nosa ordenador sabe que Z-O-O é unha palabra e non a primeira palabra é Z-O-O-H? Audiencia: [inaudível] ANDI Pengo: Exactamente, nós Quere ter a certeza de que este aquí, que é valor booleano Comprobarase fóra que é verdade. Z-O-O, a continuación, imos comprobar que, polo que sabemos exactamente, hey, xardín zoolóxico é unha palabra. Eu vou dicir a ordenador que é unha palabra tan que cando o equipo verifica, el sabe que zoo é unha palabra. Porque lembre se todos estes datos estruturas, é moi doado para nós quere dicir, oh, morcego é unha palabra. Zoo é unha palabra. Zoom é unha palabra. Pero cando está construíndo, o ordenador non ten idea. Entón tes que dicir a el exactamente en que punto é esta unha palabra? En que punto é que nin unha palabra? E en que punto I que buscar cousas, e en que punto eu teño ir a continuación? Todos clara de que? Legal. E entón vén o problema de como sería de nós ir sobre como inserir algo que, en realidade, non é? Entón imos dicir que queremos introducir a palabra, baño, na nosa trie. Como podedes ver como actualmente todo o que temos agora é B-A-T, e esta nova estrutura de datos alí tiña unha cunca que sinalou nula porque asumimos que, oh, non hai palabras tras B-A-T, por que necesitamos para manter ter as cousas despois de que T. Pero o problema xorde se quero ter unha palabra que vén despois a T. Se ten bañeira, está Vai querer un dereito H. E así, o xeito que nós estamos indo a facelo é imos crear un nó separado. Non imos poñer calquera cantidade de memoria para esta nova matriz, e imos volver a asignar punteiros. Nós imos asignar o H, Primeiro de todo, este nulo, nós estamos indo a se librar. Nós imos ter os abaixo punto H. Se vemos un H, queremos que para ir a outro lugar. Desde aquí, entón podemos marcar si. Se se loita un H despois do T, oh, entón sabemos que esta é unha palabra. O booleano vai voltar true. Todos clara sobre como isto aconteceu? Aceptar. Así, esencialmente, todo estas estruturas de datos que temos ido máis hoxe, teño ir sobre eles moito, moi rapidamente e en que non máis detalle, e iso é OK. Unha vez que comezar a xogar con el, pode manter o control de onde Todos os punteiros son, o que está a suceder na súa estruturas de datos, etcétera. Eles van ser moi útil, e cómpre a vostede caras para descubrir como totalmente fóra quere aplicar cousas. E así PSet4, de 5-- Oh, iso é incorrecto. Pset5 é erros. Como dixo antes, vai, xa de novo, descargar o código fonte de nós. Non vai ser de tres principal cousas que vai ser a descarga. Vai baixar dicionarios, KERS e textos. Todas estas cousas son son quere dicionarios de palabras que queremos que vaia ou proba de información que queremos que verificación ortográfica. E así os dicionarios nós dámoslle van para darlle palabras reais que queremos almacenar algunha maneira en forma que é máis eficiente que unha matriz. E, a continuación, os textos son será o que somos pedíndolle para deletrear comproba todas as palabras son palabras reais alí. E así os tres bloques de programas que nós imos dar-lle son chamados dictionary.c, dictionary.h, e speller.c. E así todo o dictionary.c fai é o que está invitado a aplicar. El leva palabras. El ortográfico comproba-los, e iso pasa a ser de que todo está inserida correctamente. diction.h é só un arquivo de biblioteca que declara todas esas funcións. E speller.c, nós imos dar-lle. Non precisa modificar nada diso. Todos speller.c fai é tomar que, leva-lo, verifica a velocidade do mesmo, examina o valor de referencia de como como rapidamente é capaz de facer as cousas. É un corrector ortográfico. Só non xogar con iso, pero facer seguro que entende o que está facendo. Usamos unha función chamada getrusage que examina o desempeño do seu feitizo tomada. Todo o que fai é basicamente probar a tempo de todo no seu dicionario, polo que asegúrese de comprende-lo. Teña coidado de non xogar con el ou as outras cousas non funcionará correctamente. E a maior parte dese reto é para vostedes para realmente modificar dictionary.c. Nós imos darlle 140.000 palabras nun dicionario. Nós imos dar-lle un texto ficheiro que teña estas palabras, e queremos que sexa capaz de organizar Los nunha táboa hash ou un trie porque cando pedimos-lle para deletrear check-- imaxine se é máxica comprobar como a Odisea de Homero. É como esta enorme proba enorme ,. Imaxina se cada palabra que tiña que ollar mediante unha matriz de valores de 140.000. Isto levaría para sempre para a súa máquina para funcionar. É por iso que queremos organizar a nosa datos en estruturas de datos máis eficientes como unha táboa de hash ou un trie. E entón podedes tipo de cando busca acceso cousas con máis facilidade e máis rápido. E por iso Tomé coidado para resolver colisións. Está indo a obter unha banda de palabras de que comezo con A. Vai ter unha morea palabras que comezan con B Ata caras como quere resolver. Se houbese máis función hash eficiente que só a primeira letra algo, e por iso é ata caras para tipo de facer o que quere. Quizais quere engadir todas as letras xuntas. Quizais quere como facer cousas estrañas para contabilizar o número de letras, o que quere. Ata vós como quere facer. Se queres facer unha táboa hash, se quere probar unha trie, totalmente ata. Vou aviso-lo antes de tempo que o trie é normalmente un pouco máis difícil só porque hai unha morea máis punteiros para acompañar. Pero totalmente ata vós. É moito máis eficiente na maioría dos casos. Quere realmente ser capaz de manter a par de todos os seus punteiros. Como facer o mesmo que eu estaba facendo aquí. Cando estás a introducir valores nunha táboa hash ou eliminar, asegúrese de que vostede é realmente manter o control de onde todo é porque é realmente doado para se estou intentando introducir como a palabra, Andy. Nós só dicir que é un palabra certa, a palabra, Andy, nunha lista xigante dun palabras. Se eu só terá lugar a reasignación un punteiro mal, oops, alí se vai a totalidade do o resto da miña lista ligada. Agora, a única palabra que eu ten é Andy, e agora todas as outras palabras do dicionario ser perdida. E así que quere estar seguro de que vostede manter o control de todos os seus punteiros ou entón está indo para obter enormes problemas no seu código. Debuxe as cousas con coidado, paso a paso. Isto torna moito máis doado de pensar. E, finalmente, quere ser capaz de probar o seu rendemento do seu programa no gran taboleiro. Se vós tomar unha mirar para CS50 agora, temos o que se chama o gran cadro. É a acta dos máis rápidos deletrear tempos de aferição, en todos CS50 agora, eu creo que o top 10 como veces creo que oito deles son empregados. Nós realmente queremos que vós nos vencer. Todos estabamos intentando aplicar o código máis rápido posible. Queremos que vós tentar desafiar nós e aplicar máis rápido que todos pode. E así, este é realmente a primeira vez que somos pedindo a vostedes para facer un pset que realmente pode facer en calquera método quere. Eu sempre digo, este é máis parecido a unha solución da vida real, non? Digo, hey, eu teño de ti para facelo. Construír un programa que fai isto para min. Facelo como sexa. Eu só sei que quero jejuar. Ese é o seu reto para esta semana. Vostedes, imos para darlle unha tarefa. Nós imos dar-lle un desafío. E entón cómpre a vostedes completamente só descubrir cal é a máis rápida e máis xeito eficiente de aplicar iso. Si? Audiencia: Permítese se quería buscar formas máis rápidas para facer táboas de hash en liña, podemos facer que e citar código de outra persoa? ANDI Pengo: Si, totalmente ben. Entón, se vostedes lendo spec, hai unha liña na especificación que di que vostedes son totalmente libres para buscar de hash funcións en que son algúns das funcións hash máis rápidos para realizar as cousas a través como Sempre que citar este código. Por iso, algunhas persoas xa teñen descubrín formas rápidas de facer correctores ortográficos, de rápida formas de almacenar información. Totalmente ata que vostedes se quero tomar só iso, non? Asegúrese de que está citando. O reto aquí é realmente que estamos tentando probar é que seguro que vostede sabe o camiño de volta punteiros. Tanto como aplicar a función hash real e chegando con como a matemática para facelo, podedes buscar o que quere métodos en liña que vostedes queren. Si? Audiencia: Podemos citar só usando o [inaudível]? ANDI Pengo: Si. Pode só, no seu comentario, pode citar como, oh, tomado de Yada, Yada, Yada, a función hash. Alguén ten algunha pregunta? Nós, en realidade breezed a sección de hoxe. Eu vou estar aquí a responder a preguntas ben. Ademais, como dixen, oficina horas esta noite e mañá. A especificación desta semana é, en realidade, super doado e super rápido de ler. Eu quere suxerir a ter un ollar, só ler a través da totalidade do mesmo. E Zamyla realmente anda vostede a través de cada unha das funcións precisa para aplicar, e por iso é moi, moi claro como facer todo. Só para ter seguro que é manter o control dos punteiros. Este é un pset moi reto. Non é un reto porque, como, Oh, os conceptos son moito máis difícil, ou ten que aprender moi nova sintaxe do camiño que fixo a última pset. Isto é difícil porque pset hai moitos puntos, e entón é moi, moi fácil de unha vez ten un erro no seu código non poder para descubrir onde é que o erro. E así completa e absoluta fe en ti caras para poder bater o noso [inaudível] grafías. En realidade, eu non teño ningún mina escrito Aínda non, pero estou a piques de escribir o meu. Entón, mentres está escribindo seu, eu vou estar escribindo meu. Vou tentar facer mina máis rápido que o seu. A ver quen ten o máis rápido. E si, vou ver todos vostedes aquí o martes. Vou correr un tipo como un taller pset. Todas as seccións este semana son talleres PSet, entón vostedes teñen moitas oportunidades por axuda, o horario de oficina, como sempre, e realmente ansioso para ler todo o código dos seus rapaces. Teño quizzes-se aquí se caras queren vir buscar aqueles. Iso é todo.