[Música tocando]
COLUMNA 1: Todo ben.
Todos benvidos de volta á sección.
Espero que todos están correctamente recuperado do seu quiz
desde a semana pasada.
Sei que é un pouco tolo, ás veces.
Como eu estaba dicindo antes, se está dentro do desvío estándar,
realmente non se preocupe con iso, especialmente para unha sección menos cómodo.
Isto é sobre onde debería estar.
>> Se fixo grande, entón incrible.
Kudos para vostede.
E se pensas que precisa un pouco máis de axuda, por favor
Sinto-se libre para chegar fóra a calquera dos FT.
Estamos todos aquí para axudar.
>> É por iso que nós ensinamos.
É por iso que eu estou aquí toda luns para ti rapaces e na oficina horas os xoves.
Entón, por favor, Sinto-se a liberdade de me deixar saber se está preocupado nada
ou se hai algo sobre o quiz que realmente quere abordar.
>> Así, a axenda para hoxe é todo sobre estruturas de datos.
Algunhas delas son só vai ser só para que obteña familiarizado con estes.
Non poderá aplicar los nesta clase.
Algúns deles vai, como para a súa pset ortográfico.
>> Terá a súa elección entre táboas hash e intentos.
Entón, nós imos, sen dúbida imos sobre aqueles.
Será sempre máis do tipo unha sección de alto nivel hoxe, con todo,
porque hai unha morea deles, e se fomos para os detalles de implementación
en todas elas, non teriamos mesmo pasar por listas ligadas
e quizais un pouco de táboas de hash.
>> Entón, teña paciencia comigo.
Non estamos indo facer tanto de codificación desta vez.
Se tes algunha preguntas sobre o tema ou quere ver implementado
ou probar por si mesmo, Recomendo definitivamente
indo study.cs50.net, que ten exemplos de todos estes.
Vai ter meus PowerPoints coas notas que nós
tenden a usar, así como algunha programación exercicios, sobre todo para as cousas
como listas ligadas e binario árbores pilas e suxestións.
Tan pouco máis alto nivel, que Pode ser bo para vós.
>> Entón, con iso, imos comezar.
E tamén, quizzes sim--.
Creo que a maioría de vostedes que están en miña sección ten os seus cuestionarios,
pero ninguén entra ou algún motivo non, están aquí diante.
>> Así listas ligadas.
Sei que este tipo de vai atrás antes do seu quiz.
Esa foi a semana antes que aprenden sobre iso.
Pero, neste caso, nós imos ir un pouco máis en profundidade.
>> Entón, por que poderiamos elixir un lista ligada a través dunha matriz?
Que os distingue?
Si?
>> Audiencia: Pode ampliar un conectado lista contra tamaño fixo dun array.
COLUMNA 1: Certo.
Unha matriz ten tamaño fixo mentres que unha lista ligada ten un tamaño variable.
Entón, se nós non sabemos como tanto que queremos almacenar,
unha lista ligada nos dá unha gran forma de facelo porque podemos só
engadir noutro nodo e engadir outro nó e engadir noutro nodo.
Pero o que podería ser un trade-off?
Alguén se lembra do trade-off entre matrices e listas ligadas?
Mmhmm?
>> Audiencia: Ten que percorrer todo o camiño
a través da lista ligada atopar un elemento nunha lista.
Nunha matriz, pode só atopar un elemento.
>> COLUMNA 1: Certo.
Así, con arrays--
>> Audiencia: [inaudível].
>> COLUMNA 1: Con matrices, temos o que se chama de acceso aleatorio.
Significa que, se queremos o que é xa o quinto punto dunha lista
ou o quinto punto da nosa array podemos só agarralo.
Se é unha lista ligada, temos para percorrer, non?
Entón acceder a un elemento en unha matriz é constante de tempo,
mentres que con unha lista ligada que sería probablemente será o tempo lineal, porque quizais
noso elemento é todo o camiño ao final.
Temos que buscar a través de todo.
Así, con todos estes datos estruturas que imos
gastar un pouco máis de tempo en diante, cales son os puntos positivos e negativos.
Cando podería queremos usar un sobre o outro?
E ese é o tipo de gran cousa para levar.
>> Polo tanto, temos aquí a definición dun nodo.
É como un elemento nosa lista ligada, non?
Entón, estamos todos familiarizado coas nosas estruturas typedef,
que fomos na avaliación da última vez.
Era basicamente só crear outro tipo de datos que poderiamos usar.
>> E neste caso, é un nó que realizará algún enteiro en.
E entón o que é a segunda parte aquí?
Calquera?
>> Audiencia: [inaudível].
>> COLUMNA 1: Si.
É un punteiro ao seguinte nodo.
Polo tanto, este debe realmente estar aquí enriba.
Este é un tipo de punteiro nó á seguinte cousa.
E iso é o que eles engloba o noso nó.
Legal.
>> Todo ben, entón coa investigación, como estabamos só dicindo antes da man, se está
vai investigar, ten que realmente facer unha iteración
a través da súa lista ligada.
Entón, se nós estamos mirando para o número 9, que comezaría na nosa cabeza
e que nos sinala para o inicio da nosa lista ligada, non?
E nós dicimos: OK, fai iso nó conter o número 9?
Non?
>> Todo ben, vaia á seguinte.
Siga o.
Será que contén o número 9?
Non.
Segue o próximo.
>> Entón temos que realmente iteración a través da nosa lista ligada.
Non podemos simplemente ir directamente onde 9 é.
E se vostedes realmente queren ver algúns pseudo-código alí enriba.
Temos algunha función de busca aquí que leva em-- o que fai falta en?
¿Que pensas?
Unha tan fácil.
¿Que é iso?
Audiencia: [inaudível].
COLUMNA 1: O número que estamos buscando.
Non?
E o que sería iso corresponde a?
É un punteiro para?
>> Audiencia: un nó.
>> COLUMNA 1: Un nó á lista que nós estamos mirando, non?
Polo tanto, temos algúns nós son punteiro aquí.
Este é un punto que vai realmente iterado nosa lista.
Nós configure-lo igual a lista porque iso é só
fixándose a igual ao inicio da nosa lista ligada.
>> E mentres non se NULL, mentres aínda temos cousas na nosa lista,
comprobar a ver se ese nodo ten o número que estamos buscando.
Devolve certo.
Se non, actualiza-lo, non?
>> De ser NULL, saímos nosa while e voltar falso
porque iso significa que non telo atopado.
Será que todo o mundo comeza como funciona isto?
Está ben.
>> Así, coa inserción, ten ter tres formas diferentes.
Pode preceder, pode engadir e pode introducir en sorte.
Neste caso, estamos vai facer un preceder.
Alguén sabe como aqueles tres casos pode ser diferente?
>> Entón preceder significa que poñer el diante da súa lista.
Entón, isto significa que non importa que o nodo é, non importa
cal é o valor, vai para poñelas aquí diante, OK?
Será o primeiro elemento na súa lista.
>> Se anexo-lo, que vai para ir á parte de atrás da súa lista.
E inserir en variados significa que está vai poñer realmente no lugar
onde mantén a súa lista ligada ordenada.
Unha vez máis, como se usa os e cando usa
vai ser variar segundo o caso.
Se non ten ser clasificado, anteposta tende
ser o que a maioría da xente usar, porque non fai
Ten que pasar por toda a lista para atopar o fin de engadir lo, non?
Pode simplemente poñelas dereito.
>> Entón, imos pasar por un inserción 1 agora.
Entón, unha cousa que eu vou recomendo neste pset
é chamar as cousas, como sempre.
É moi importante que actualice os punteiros na orde correcta
porque se actualiza-los un pouco fóra de orde,
vai acabar perda de partes da súa lista.
>> Así, por exemplo, neste caso, estamos contando a cabeza para só un punto a 1.
Se nós só facelo sen gardar este 1,
nós non temos ningunha idea do que 1 debería apuntar agora
porque perdemos o cabeza apuntada.
Entón, unha cousa para lembrar cando está facendo un preceder
é gardar o que o cabeza puntos para o primeiro,
Despois, asigne-o e actualiza o que o seu novo nodo debe apuntar.
Neste caso, esta é unha forma de facelo.
>> Entón, se tivésemos feito isto dese xeito onde nós só trasladado cabeza,
perdemos basicamente nosa lista enteira, non?
Unha forma de facelo é ter un punto de seguinte, e despois ter punto cabeza para 1.
Ou pode facer como o tipo de almacenamento temporal, de que falei.
>> Pero a reatribuição seu punteiros na orde correcta
vai ser moi, moi importante para este pset.
Se non, vai ter un hash mesa ou un intento que só será
só unha parte das palabras que quere e entón you're-- mmhmm?
Audiencia: Cal foi o temporal cousa de almacenamento que estaba falando?
COLUMNA 1: O almacenamento temporal.
Entón, basicamente, outra xeito que podería facelo
é almacenar o xefe de algo, como almacena-lo na variable temporal.
Atribuílo la a un e logo actualizar 1 ao punto
para calquera cabeza usado para ligar a.
Deste xeito é obviamente máis elegante, porque
Non é necesario un valor temporal, pero só ofrecer outra forma de facelo.
E nós realmente temos un código para esta.
Así, para lista ligada, nós realmente ten algún código.
Entón, introduza aquí, este é antecedendo.
Polo tanto, este entra nel na cabeza.
>> Entón o primeiro, ten que crear o seu novo nodo, por suposto,
e comprobar se hai NULL.
Sempre é bo.
E entón tes que para asignar os valores.
Sempre que crea un novo nodo, ten Non sei o que está a apuntar cara ao próximo,
así que quere arrincar para NULL.
Se acabar apuntando a algo outra cousa, é trasladado e está todo ben.
Se é o primeiro na lista, el que
para ligar a NULL porque iso é o final da lista.
>> Entón para inserir-lo vemos aquí está atribuíndo o seguinte valor do noso nodo
para ser o cabeza, que é o que tivemos aquí.
Iso é o que nós fixemos.
E entón nós estamos atribuíndo cabeza para punto ao noso novo no, porque lembre,
é algún novo punteiro para un nó, e iso é o que é cabeza.
É exactamente por iso que ten ese asesor frecha.
Legal?
Mmhmm?
>> Audiencia: Será que temos que arrincar novo xunto a NULL en primeiro lugar,
ou podemos simplemente arrinque-lo de cabeza?
>> COLUMNA 1: New próxima ten que ser NULL para iniciar
porque non sabe onde vai ser.
Ademais, esta é unha especie de Así como un paradigma.
Vostede define-lo igual a NULL só para facer Asegúrese de que todas as bases están cubertas
antes de facer calquera cambio de modo que está sempre garantido que vai
estar apuntando para un valor específico contra como un valor de lixo.
Porque, si, nós atribuímos novo xunto automaticamente,
pero é máis como unha boas prácticas para arrincar
desa forma e despois transferir.
>> OK, entón dobremente ligada listas agora.
Que pensamos?
O que hai de diferente con dobremente ligada listas?
>> Así, nas nosas listas ligadas, podemos só mover nunha dirección, non?
Nós só temos a continuación.
Nós só podemos ir á fronte.
>> Cunha lista dobremente ligada, Tamén podemos andar para tras.
Polo tanto, temos non só a número que desexa almacenar,
temos onde apunta ao seguinte e onde veu.
Entón, iso permite algúns mellores travesía.
>> Entón nós dobremente vinculadas, moi semellante, non?
A única diferenza é que agora teñen unha banda e unha anterior.
É a única diferenza.
>> Entón, se fósemos para preceder ou append-- nós non teñen ningunha código para esta aquí - se
pero se fose para intentar inserir-lo, o importante
é que ten que facer Asegúrese de que está asignando
tanto o anterior eo seu preto punteiro correctamente.
Polo tanto, neste caso, faría non só arrincar seguinte,
vostede arrinque anterior.
Se estamos na parte superior da lista, nós non só facer a cabeza igual novo,
pero debe ser a nosa nova anterior apuntar á cabeza, non?
>> Esa é a única diferenza.
E se queres máis práctica con estes con listas ligadas, coa inserción,
coa exclusión, coa inserción nunha lista variada,
confía study.cs50.net.
Hai unha morea de grandes exercicios.
Recomendo a eles.
Gustaríame que tivésemos tempo para pasar por eles pero hai unha morea de estruturas de datos
para pasar.
>> OK, entón táboas de hash.
Este é probablemente o máis pouco útil para a súa pset
aquí, porque vai ser implantación dun destes, ou un intento.
Realmente me gusta de táboas de hash.
Son moi legal.
>> Entón, basicamente, o que pasa é unha táboa hash
é cando nós realmente necesitamos Speedy inserción, exclusión e investigación.
Estas son as cousas que estamos priorizar nunha táboa hash.
Poden ser moi grande, mais, como veremos, con intentos,
hai cousas que son moi grandes.
>> Pero, basicamente, todo un hash táboa é unha función hash
que lle di que balde para que cada dos seus datos, cada un dos seus elementos en.
Un xeito sinxelo de pensar nunha táboa hash é que non é só baldes de cousas,
non?
Entón, cando está clasificando as cousas por como a primeira letra do seu nome,
que é como unha especie de táboa de hash.
>> Entón, se eu fose vostedes grupo é en grupos de quen quere que o seu nome comeza
cun aquí, ou quen queira que o aniversario é en xaneiro, febreiro, marzo,
sexa cal sexa, que é eficaz creación dunha táboa hash.
É só crear baldes que clasificar os elementos en
para que poida atopalos máis fácil.
Así, deste xeito, cando eu teño para atopar un de vós,
Non teño que buscar a través de cada un dos seus nomes.
Podo ser como, oh, sei que Aniversario de Danielle é em--
Audiencia: --April.
COLUMNA 1: abril.
Entón eu ollo na miña abril balde, e con algunha sorte,
vai ser a única persoa dentro, e meu tempo era constante nese sentido,
mentres que, se eu teño que mirar a través dun grupo enteiro de persoas,
que vai levar moito máis tempo.
Entón, táboas hash son realmente só baldes.
Un xeito doado de pensar deles.
>> Entón, unha cousa moi importante sobre unha táboa hash é unha función hash.
Entón, as cousas que eu acabo de falar, como súa primeira letra do seu nome
ou o mes de aniversario, estas son ideas que
realmente se correlacionam cunha función hash.
É só un xeito de decidir que balde está elemento entra, OK?
Polo tanto, para este pset, pode ollar para arriba practicamente calquera función hash que quere.
>> Non ten que ser o seu propio.
Hai algúns realmente fresco fóra hai que facer todo tipo de matemáticas tolo.
E se quere facer o seu corrector ortográfico super rápido,
Eu definitivamente ollar a un destes.
>> Pero hai tamén o son máis simple, como a computación
a suma das palabras, como cada letra ten un número.
Calcular a suma.
Que determina o balde.
Eles tamén teñen as máis fáciles que son só como toda a dun aquí,
todo o B está aquí.
Calquera destes.
>> Basicamente, el só dille que índice da matriz seu elemento debe ir.
Basta decidir bucket-- é todo unha función hash é.
Polo tanto, temos aquí un exemplo que é só a primeira letra da cadea
que eu estaba falando.
>> Entón ten algún hash que é só o primeira letra da frase, menos un,
que lle dará algúns número entre 0 e 25.
E o que quere facer é asegúrese de que isto representa
o tamaño do seu hash de mesa-- cantos baldes existen.
Con moitos destes funcións de hash, son
será o regreso de valores que pode estar moi por riba do número de depósitos
que realmente ten na súa táboa de hash,
entón tes que facer Asegúrese e mod por aqueles.
Se non, que vai dicir, Oh, el debe estar en balde 5000
pero só ten 30 baldes na súa táboa hash.
E, por suposto, todos sabemos que é vai producir algúns erros de tolos.
Entón asegúrese de mod polo tamaño da táboa hash.
Legal.
Así colisións.
Están todos ben ata agora?
Mmhmm?
>> Audiencia: Por que voltar un valor tan grande?
>> COLUMNA 1: En función do algoritmo que a súa función de hash usa.
Algúns deles han facer multiplicación tolo.
E é todo sobre a obtención de unha distribución uniforme,
para que realmente facer algunha cousas malucas ás veces.
Iso é todo.
Algo máis?
Está ben.
>> Así colisións.
Basicamente, como dixen anteriormente, no mellor dos casos,
calquera balde eu ollar é terá unha cousa,
entón eu non teño que mirar para todo, non?
Eu non sei que está aí ou é Non, e iso é o que realmente queremos.
Pero se temos decenas de miles de Os puntos de datos e inferior a ese número
de baldes, nós imos ter colisións onde finalmente algo
terá que acabar nun balde que xa ten un elemento.
>> Entón a pregunta é, o que que imos facer nese caso?
O que imos facer?
Xa temos algo alí?
Será que simplemente xoga-lo fóra?
>> Non.
Temos que manter os dous.
Así, a forma que nós normalmente facelo é o que?
Cal é a estrutura de datos que acabamos de falar?
Audiencia: lista encadeada.
COLUMNA 1: Unha lista ligada.
Entón, agora, en vez de cada un destes baldes ter só un elemento,
que vai conter unha lista ligada de os elementos que foron hash dentro del.
OK, que todos tipo de tirou esa idea?
Porque nós non poderiamos ter un array por que non sabemos cantas cousas
van estar alí.
Unha lista ligada permítenos ter só o número exacto que
son mesturados que balde, non?
>> Entón lineal de sondaxe é basicamente este idea--
é unha forma de xestionar a colisión.
O que podes facer é, neste caso, baga foi hash nun
e xa temos algo alí, só
siga indo para abaixo ata atopa un slot baleiro.
Esta é unha forma de tratar con isto.
A outra forma de xestionar é co que acabamos de
called-- o conectado lista chámase fío.
>> Entón, esa idea funciona se súa táboa hash que pensa
é moito maior que seu conxunto de datos ou se
quero tentar minimizar o encadeamento ata que sexa absolutamente necesario.
Entón, unha cousa é lineal enquisa, obviamente, significa
que a súa función de hash non é tan útil
porque vai acabar empregando súa función de hash, quedando a un punto,
vostede lineal sondar ata nalgún lugar que está dispoñible.
Pero agora, por suposto, nada outra cousa que acaba por alí,
vai ter que buscar aínda máis abaixo.
>> E hai moito máis gasto de busca que
vai á introdución dun elemento na súa táboa hash agora, non?
E agora cando vai tentar atopar baga de novo, vai botar el,
e que vai dicir: Oh, mira no balde 1,
e non será no balde 1, entón está
terá que atravesar a través do resto destes.
Entón, ás veces é útil, pero na maior parte dos casos,
imos dicir que encadeamento é o que quere facer.
>> Entón nós falamos sobre iso antes.
Eu teño un pouco por diante de min.
Pero o fío é basicamente que cada balde na súa táboa hash
é só unha lista ligada.
>> Así, outra forma, é máis técnico forma, pensar nunha táboa hash
é que non é só unha matriz de listas ligadas, que
cando está escribindo o seu dicionario e estás cargalo,
pensar niso como unha matriz de listas ligadas
fará que sexa moito máis fácil para que poida arrincar.
>> Audiencia: Entón táboa hash ten un tamaño pre-determinado,
como un [inaudível] de baldes?
>> COLUMNA 1: Certo.
Por iso, ten un número definido de baldes que determine--
que vostedes deben Sinto-se libre para xogar.
Pode ser moi legal a ver que pasa
como cambiar o seu número de caçamba.
Pero si, el ten un definir o número de baldes.
O que lle permite encaixar como moitos elementos que precisa
é este fío separado onde ligaron listas en cada balde.
Isto significa que a súa táboa hash será exactamente o tamaño
que precisa que sexa, non?
Ese é o punto de listas ligadas.
Legal.
>> Por iso, todos OK alí?
Todo correcto.
Ah.
Que pasou?
Realmente agora.
Creo que alguén está me matando.
>> OK, imos entrar intentos, que son un pouco tolo.
Gústame táboas de hash.
Eu creo que son moi legal.
Tries son legais tamén.
>> Entón, alguén se lembra o que é un intento?
Debería ir máis brevemente na charla?
Vostede recorda do tipo de como funciona?
Audiencia: Eu só estou bailando que pasar por iso.
COLUMNA 1: Non pasar por iso.
OK, nós realmente estamos indo a ir sobre el agora é o que estamos dicindo.
>> Audiencia: Isto é para unha árbore de recuperación.
>> COLUMNA 1: Si.
É unha árbore de recuperación.
Impresionante.
Entón, unha cousa a notar aquí é que nós Está mirando para caracteres individuais
aquí, non?
>> Polo tanto, antes coa nosa función de hash, que estaban mirando para as palabras como un todo,
e agora estamos a buscar máis aos personaxes, non?
Polo tanto, temos Maxwell aquí e Mendel.
Entón, basicamente, un try-- unha forma de pensar sobre iso é que todos os niveis aquí
é unha matriz de letras.
Polo tanto, este é o nó raíz aquí, non?
Isto ten todos os personaxes do alfabeto ao comezo de cada palabra.
>> E o que quere facer é digamos, OK, temos algunha palabra M.
Nós imos ollar para Maxwell, de xeito imos para M. e M apunta a un enteiro
outra matriz onde cada palabra, mentres haxa
é unha palabra que ten un como a segunda carta,
mentres que hai unha palabra que ten B como a segunda carta,
terá un punteiro indo a algunha próxima matriz.
>> Probablemente non hai unha palabra que MP algo,
Así, coa posición P no presente array, que sería só NULL.
El diría: OK, non hai ningunha palabra que M seguido por un P, OK?
Entón, se pensamos sobre iso, cada unha desas cousas pequenas
é realmente un destes grandes conxuntos de A a Z.
Entón, o que pode ser unha das cousas que é unha especie de desvantaxe de un intento?
>> Audiencia: Unha gran cantidade de memoria.
>> COLUMNA 1: É unha tonelada de memoria, non?
Cada un destes bloques aquí representa 26 espazos, 26 matriz elemento.
Entón intenta estar incrible pesada espazo.
>> Pero son moi rápidos.
Entón, incrible rápido, pero realmente espazo ineficiente.
Medio que ten que descubrir cal deles quere.
Estes son moi legal para a súa pset, pero eles ocupan moita memoria,
para que o comercio off.
Si?
>> Audiencia: Sería posible configurar un intento e, a continuación,
xa que ten todo o datos en que need--
Non sei se isto tería sentido.
Eu estaba me librar de todo o Caracteres nulos, pero, a continuación,
non sería capaz de indexar eles--
>> COLUMNA 1: Aínda que deles.
>> Audiencia: - do mesmo xeito cada vez.
COLUMNA 1: Si.
Debe dos caracteres nulos para deixar Vostede sabe se non hai unha palabra alí.
Ben se ten algo que quere?
Está ben.
Todo ben, entón imos para ir un pouco máis
no detalle técnico atrás intentando traballar cun exemplo.
>> OK, entón iso é o mesmo.
Considerando que, nunha lista ligada, a nosa principal tipo de-- cal é a palabra que quero? -
como a construción de bloque era un nó.
Nun intento, nós tamén temos un nó, pero defínese de forma diferente.
>> Polo tanto, temos algúns que bool representa, en realidade, se unha palabra
existe neste lugar, e logo, temos algunha variedade aqui-- ou mellor,
este é un punteiro para unha matriz de 27 caracteres.
E dicir, para, no presente caso, este 27-- Estou seguro que todos vostedes son como, espera,
hai 26 letras no alfabeto.
Por que temos 27?
>> Así, dependendo do forma de aplicar esta,
dicir dun pset que permitiu apóstrofos.
É por iso que o extra.
Tamén terá nalgún casos o terminador nulo
está incluída como un dos caracteres que se admite ser,
e é así que eles verifican a ver se é o final da palabra.
Se vostede está interesado, confía Vídeo de Kevin en study.cs50,
así como a Wikipedia ten uns bos recursos alí.
>> Pero imos pasar por só unha especie de como pode traballar a través dun intento
se está dado un.
Polo tanto, temos unha super sinxelo aquí que Ten as palabras "bat" e "zoom" neles.
E como vemos aquí enriba, este pequeno espazo aquí
representa o noso bool que di, si, esta é unha palabra.
E entón iso ten a nosa arrays de caracteres, non?
>> Entón, nós estamos indo a percorrer atopar "morcego" nesa intento.
Entón comeza na parte superior, non?
E sabemos que b corresponde a o segundo índice, o segundo elemento
Nesta matriz, porque a e b.
Así, preto de un segundo.
>> E di, Aceptar, legal, segue que en a seguinte matriz, porque se nos lembrar,
non é que cada un destes en realidade, contén o elemento.
Cada unha destas matrices contén un punteiro, non?
É unha distinción importante a facer.
>> Sei que iso vai ser-- intentos son realmente difícil de obter o primeiro tempo,
polo que aínda que este é o segunda ou terceira vez
e aínda é o tipo de parecer difícil,
Eu prometer que se vai asistir o mañá curto de novo,
probablemente vai facer moito máis sentido.
Leva moito para dixerir.
Eu ás veces aínda son como, espera, o que é un intento?
Como eu uso iso?
>> Entón temos b neste caso, que é o noso segundo índice.
Se tivésemos, por exemplo, c ou d ou calquera outra carta,
necesitamos mapear que volve ao índice da nosa matriz que que corresponde a.
Entón, nós tomaríamos como rchar e nós só restar fóra dun para mapea-lo en 0-25.
Todo o mundo bo como nós mapear os nosos personaxes?
Está ben.
>> Entón imos para a segunda e nós ver que, si, el non é NULL.
Podemos pasar ao seguinte matriz.
Entón imos ao seguinte conxunto aquí.
>> E nós dicimos: OK, agora nós que ver se un está aquí.
É un nulo ou non é realmente seguir adiante?
Así, en realidade, un move encamiñar nesta matriz.
E nós dicimos: OK, t é a nosa última carta.
Entón imos ao t no índice.
E, entón, avanzar porque non hai outro.
E iso se di, basicamente, que, si, el di que non é unha palabra aquí-
que, se seguir este camiño, chegou
nunha palabra, que sabemos que é "bat".
Si?
>> Audiencia: É normal ter que como índice 0 e, a continuación, ter unha especie en 1
ou para ter ao final?
>> COLUMNA 1: Non.
Polo tanto, se miramos para o noso declaración aquí, é un bool,
polo que é o seu propio elemento no seu nó.
Polo tanto, non é parte da matriz.
Legal.
Entón, cando nos terminais a nosa palabra e estamos nesta matriz, o que queremos facer
é facer unha comprobación para iso é unha palabra.
E neste caso, el volvería si.
>> Entón, nesa nota, sabemos que "zoo" - sabemos como os seres humanos que "zoo" é unha palabra,
non?
Pero se tentar aquí sería dicir, non, non é.
E diría que porque nós non designouno como unha palabra aquí.
Aínda que poden atravesar a través do presente matriz,
este intento diría que non, zoolóxico non está no seu dicionario
porque non temos designado como tal.
>> Así, un xeito de facer isso-- Ah, desculpe, este.
Polo tanto, neste caso, "zoo" non é unha palabra, pero é na nosa intento.
Pero neste, dicir que quere que el introducir a palabra "baño", o que pasa
é seguirmos through-- b, un t.
Estamos nesa matriz, e imos para buscar h.
>> Neste caso, cando mirar para o punteiro no h,
está a apuntar cara NULL, OK?
Entón, a menos que sexa explicitamente apuntando a outra matriz,
asumir que todo punteiros nesta matriz están apuntando para null.
Polo tanto, neste caso, h está apuntando como nulo polo que non podemos facer nada,
polo que sería tamén volver falsa, "baño" non é aquí.
Polo tanto, agora estamos realmente vai pasar por
como é que nós realmente dicir que "zoo" é na nosa intento.
Como é que imos introducir "zoo" na nosa intento?
Así, do mesmo xeito que comezou co nosa lista ligada, comezan na raíz.
Cando estea en dúbida, comece a raíz destas cousas.
>> E imos dicir, OK, z.
z existe neste, e fai.
Entón está movendo súa próxima matriz, OK?
E entón o próximo, podemos dicir, OK, se o hai?
Fai.
Este novo.
>> E así, no noso próximo, dixemos, OK, "zoo" xa existe aquí.
Todo o que necesitamos facer é establecer este xeito a verdade, que non é unha palabra alí.
Se tivese seguido todo ata antes dese punto,
é unha palabra, polo que só configure-lo igual a tal.
Si?
>> Audiencia: Entón fai iso significa que "ba" é unha palabra tamén?
>> COLUMNA 1: Non.
Polo tanto, neste caso, "ba" obteriamos aquí, diriamos que é unha palabra,
e inda sería non.
Ok?
Mmhmm?
>> Audiencia: Entón, cando é un palabra e di que si, el
conterá a ir m?
>> COLUMNA 1: Entón, isto ten que ver com-- está cargando iso en.
Vostede di "zoo" é unha palabra.
Cando vai a check-- como, digamos que quere dicir,
significa "zoo" existe neste dicionario?
Só vai buscar "zoo" e, a continuación, comprobar a ver se é unha palabra.
Vostede non vai moverse mediante m por iso non é
o que está a procurar.
>> Entón, se nós realmente quería engadir "baño" neste intento,
fariamos o mesmo como fixemos con "zoo"
excepto veriamos que cando nós tentar chegar o momento, non existe.
Entón pode pensar niso como un intento para engadir un novo nodo nunha lista ligada,
de xeito que sería necesario para engadir outro unha desas matrices, así.
E entón o que facemos é só definir o h elemento desa matriz apuntando para iso.
>> E entón, o que quere facer aquí?
Engadir lo igual a true porque é unha palabra.
Legal.
Sei.
Tenta non son o máis emocionante.
Confío en min, sei.
>> Entón, unha cousa a entender con intentos, Eu dixen, son moi eficientes.
Entón, nós vimos eles levar ata unha tonelada de espazo.
Son o tipo de confundir.
Entón, por que nós nunca usalos?
Usan estes porque son incrible eficiente.
>> Entón, se está sempre buscando unha palabra, só son
delimitada pola lonxitude da palabra.
Entón, se está a buscar un palabra que ten unha lonxitude de cinco,
está sempre só terá que facer, como máximo, cinco comparacións, OK?
Así, torna-se, basicamente, unha constante.
Como a inserción e investigación son basicamente constante de tempo.
>> Entón, se pode nunca chegar algo en tempo constante,
que é tan bo como el gañou.
Non pode ir mellor do que constante de tempo para estas cousas.
Así que é un dos enormes vantaxes de intentos.
>> Pero é moito espazo.
Entón medio que ten que decidir o que é máis importante para vostede.
E en computadores de hoxe, o espazo que un intento pode levar ata
quizais non afecta que moito, pero quizais
está lidando con algo que ten moito, moito máis cousas,
e un intento só non é razoable.
Si?
>> Audiencia: Agarde, entón ten 26 letras en cada un?
>> COLUMNA 1: Mmhmm.
Si, ten 26.
Ten algunha é marcador de texto e, a continuación, ten 26 indicadores en cada un.
E eles están ponto--
>> Audiencia: E cada 26 anos, que cada un deles ten 26?
>> COLUMNA 1: Si.
E é por iso que, como pode ver, el se expande rapidamente.
Todo correcto.
Entón, nós estamos indo a entrar en árbores, o que Eu sinto que é máis fácil e, probablemente,
ser un pouco agradable indulto desde intentos alí.
Polo tanto, agardamos que a maioría de vós vin unha árbore antes.
Non como o bastante os de fóra, que eu
Non sei se alguén foi ao ar recentemente.
Fun colleita da mazá este fin de semana, e Oh meu Deus, el era fermoso.
Eu non sabía que as follas podería parecer que fermosa.
>> Polo tanto, esta é só unha árbore, non?
É só un nó, e apunta a unha morea de outros nós.
Como pode ver aquí, este é tipo de un tema recurrente.
Nodes apuntando para nós é unha especie de a esencia de moitas estruturas de datos.
Depende só de como nós telos uns a outros para apuntar
e como nós percorremos a través deles e como nós
inserir cousas que determina as súas diferentes características.
>> Entón, só tes que algo de terminoloxía, que eu usei antes.
Entón raíz é o que está na parte superior.
É onde sempre comezar.
Pode pensar niso como a cabeza tamén.
Pero, para as árbores, que tenden a se refiren a el como a raíz.
>> Calquera cousa no fondo aqui-- no moi, moi bottom--
follas son consideradas.
Por iso, vai xunto co cousa árbore enteira, non?
As follas son nos bordos da súa árbore.
>> E despois temos tamén un par de canto de falar de nós en relación
uns cos outros.
Polo tanto, temos pai, fillos e irmáns.
Polo tanto, neste caso, é o 3 -Nai de 5, 6, e 7.
Entón, o pai é o que está un paso por riba de todo o que está a
referíndose se, polo que só como unha árbore xenealóxica.
Afortunadamente, iso é todo un pouco pouco máis intuitivo que os intentos.
>> Os irmáns son os que teñen o mesmo pai, non?
Eles están no mesmo nivel aquí.
E entón, como eu estaba dicindo que os fillos son só
todo o que é un chanzo por baixo o no en cuestión, OK?
Legal.
Así, unha árbore binaria.
Alguén pode arriscar un palpite nun dos as características da árbore binaria?
>> Audiencia: Max dúas follas.
>> COLUMNA 1: Certo.
Así máximo de dúas follas.
Así, nun presente antes, tivemos un regalo que tiña tres, pero dunha árbore binaria,
ten un máximo de dous nenos por pais, non?
Hai outro característica interesante.
Alguén sabe iso?
Árbore binaria.
>> Así, unha árbore binaria terá todo en as-- este non é sorted--
pero dunha árbore binaria clasificados, todo á dereita
é maior que a nai, e todo á esquerda
é menor que a nai.
E iso foi un quiz pregunta antes, entón é bo saber.
Entón, o xeito no que definimos tanto, de novo, temos outro nodo.
Este é moi parecido ao que?
Dobremente
>> Audiencia: Linked listas
>> COLUMNA 1: Unha lista ligada dobre, non?
Entón, se substituírmos este con anterior e seguinte,
esta sería unha lista dobremente ligada.
Pero, neste caso, nós realmente ter esquerda e dereita e é iso.
Se non, é o mesmo.
Aínda temos o elemento está a buscar,
e só ten dous punteiros indo ao que vén a continuación.
Si, entón árbore binaria de busca.
Se se decata todo no aquí é maior than--
ou todo inmediatamente a dereita aquí
é maior que, todo aquí é inferior a.
>> Entón, se fósemos buscar, el que mirar moi preto de procura binaria
aquí, non?
Excepto no canto de mirar na metade da matriz,
estamos só mirando para a esquerda ou lado ou do lado dereito da árbore.
Entón, el está un pouco máis simple, eu creo.
>> Polo tanto, se a súa raíz é NULL, obviamente, é simplemente falso.
E se está alí, obviamente, é verdade.
De ser menor que, buscamos a esquerda.
De ser maior que, buscamos a dereita.
É exactamente como busca binaria, só unha estrutura de datos diferente
que estamos a usar.
En vez dunha matriz, é só unha árbore binaria.
>> OK, pilas.
E tamén, parece que pode ter un pouco de tempo.
Se facemos iso, estou feliz de ir sobre nada diso de novo.
OK, entón apilar.
Alguén recorda o que stacks-- calquera características dunha pila?
>> OK, así que a maioría de nós, eu creo, comer na cea halls--
tanto como nós pode non gustar.
Pero, obviamente, pode pensar en unha pila literalmente só como unha pila de bandexas
ou unha pila de cousas.
E o que é importante para entender é que é
something-- a característica que podemos chamalo por-- é LIFO.
Alguén sabe o que significa isto?
Mmhmm?
>> Audiencia: último a entrar, primeiro en saír.
>> COLUMNA 1: Dereito, último a entrar, primeiro en saír.
Entón, se sabemos si imos apilar as cousas se, a cousa máis fácil de coller off--
e quizais o único que pode incorporarse off, a nosa pila é grande enough--
é aquel elemento superior.
Entón o que foi posto en last-- como vemos aquí,
todo o que foi empurrado na maioría recently-- é
será o primeiro cousa que nós pop off, OK?
>> Entón o que temos aquí é outra struct typedef.
Isto é realmente só como un Bater Curso de estrutura de datos,
por iso hai moito xogado vós.
Sei.
Entón, unha struct.
Yay para estruturas.
>> E neste caso, é un punteiro para unha matriz que ten algunha capacidade.
Entón, iso representa a nosa pila aquí, como a nosa matriz real
que está sostendo os nosos elementos.
E entón aquí temos algúns tamaño.
>> E xeralmente, quere manter pista de quão grande é a túa stack
porque o que permitirá cómpre facer é se sabe o tamaño,
el permite que di, OK, eu son a capacidade?
Podo engadir algo máis?
E tamén lle di onde a parte superior do seu stack
É así que sabe o que pode realmente despegar.
E iso realmente vai ser un pouco máis claro.
>> Así, por impulso, unha cousa, se nunca foron para aplicar impulso,
como eu estaba dicindo, o pila ten un tamaño limitado, non?
A nosa matriz tiña algunha capacidade.
É unha matriz.
É un tamaño fixo, polo que necesitamos asegúrese de que non estamos poñendo máis
na nosa matriz do que nós realmente ten espazo para.
>> Entón, cando está creando un impulso función, o primeiro que fai é dicir, OK,
eu teño espazo na miña pila?
Porque se eu non fai iso, desculpe, Non podo gardar o seu elemento.
Se eu fai iso, entón quere almacenar Lo na parte superior da pila, á dereita?
>> E é por iso que temos manter o control do noso tamaño.
Se non manter o control do noso tamaño, Non sabemos onde poñelas.
Non sabemos cantas cousas están na nosa matriz xa.
Como evidentemente hai formas que quizais podería facelo.
Pode arrincar todo para NULL e, a continuación, comproba o último NULL,
pero unha cousa moito máis fácil é só quere dicir, OK, manter o control de tamaño.
Como sei que eu teño catro elementos na miña matriz, entón a seguinte cousa
que poñer, somos indo para almacenar o índice 4.
E entón, por suposto, isto significa que vostede empurrou algo correctamente
no seu stack, ten quere aumentar o tamaño
para que vostede sabe onde está a que pode empurrar máis cousas sobre.
>> Entón, se estamos tentando pop algo fóra da pila,
o que podería ser o primeiro que quere comprobar?
Estás a tomar algo fóra da súa pila.
Está seguro de que hai algo na súa pila?
Non.
Entón, o que podemos querer comprobar?
>> Audiencia: [inaudível].
COLUMNA 1: Comprobe o tamaño?
Tamaño.
Por iso, queremos comprobar se noso tamaño é maior que 0, OK?
E se é, entón queremos diminuír noso tamaño por 0 e voltar iso.
Por que?
>> No primeiro fomos empurrando, nós empurrou
sobre o tamaño eo tamaño actualizado.
Neste caso, estamos diminuíndo o tamaño e despois tiralo, arrancando-o
da nosa matriz.
Por que facemos isto?
Entón, se eu teño unha cousa na miña pila, cal sería o meu tamaño en que punto?
1.
>> E onde está almacenado o elemento 1?
En que índice?
Audiencia: 0.
COLUMNA 1: 0.
Polo tanto, neste caso, nos sempre que facer sure--
no canto de volver tamaño menos 1, porque nós
saber que o noso elemento é será almacenado a unha menor
calquera que sexa o noso tamaño é, este só coida del.
É un xeito un pouco máis elegante.
E nós só diminuír a nosa tamaño e, a continuación, voltar tamaño.
Mmhmm?
>> Audiencia: Creo que só en xeral, por que esta estrutura de datos
ser beneficioso?
>> COLUMNA 1: Depende do seu contexto.
Así, para algunhas das teorías, se está a traballar com-- OK,
déixeme ver se hai un beneficioso que é beneficioso para máis de fóra
de CS.
Con pilas, a calquera hora que precisa manter o control de algo que
é o engadido máis recentemente é cando vai querer usar unha pila.
>> E eu non podo pensar en unha boa exemplo do que agora.
Pero sempre que a última cousa é máis importante para vostede,
que é cando unha pila será útil.
Estou intentando pensar se hai unha boa para iso.
Se eu pensar nun bo exemplo na seguinte 20 minutos, seguramente vou che dicir.
>> Pero en xeral, se hai algo, como dixen a maioría, onde máis recente
é o máis importante, que é onde unha pila entra en xogo.
Considerando as filas son unha especie de oposto.
E todos os cans pequenos.
Non é esta a gran, non?
Eu sinto que eu debería só ten un video coello
á dereita no medio sección para vós
porque este é un corte intenso.
>> Entón unha cola.
Basicamente, unha fila é como unha liña.
Vostedes Estou seguro de que uso iso todos os días, así como nas nosas salas de cea.
Entón, nós temos que ir en e chegar nas nosas bandexas, eu son
se ten que esperar na cola para roubar ou obter o seu alimento.
>> Así, a diferenza aquí é que este é o FIFO.
Entón, se LIFO foi o último en entrar, primeiro fóra, FIFO é o primeiro en entrar, primeiro fóra.
Polo tanto, este é o lugar onde todo o que poñer en primeiro lugar é a súa máis importante.
Entón, se estaba esperando nun linha-- pode vostede
imaxina se fose a ir buscar o novo iPhone
e era unha pila en que a última persoa da cola chegou primeiro,
a xente ían matar un ao outro.
>> Entón FIFO, estamos todos moi familiarizado con no mundo real aquí,
e todo isto ten que ver coa realidade tipo de recrear esta liña enteira
e colas estrutura.
Así, mentres que coa pila, temos push pop.
Cunha cola, temos enfileiramento e retirar da cola.
Entón enfileiramento significa, basicamente, poñelas na parte de atrás,
e medios dequeue tomar fóra a partir da fronte.
Polo tanto, a nosa estrutura de datos é un pouco máis complicado.
Temos unha segunda cousa a seguir.
>> Así, sen a cabeza, esta é exactamente unha pila, non?
Esta é a mesma estrutura que unha pila.
O único diferente agora é que ten esa cabeza, que o que pensa
vai seguir?
>> Audiencia: O primeiro.
>> COLUMNA 1: Dereito, o primeiro que poñemos no.
O xefe da nosa fila.
Quen é o primeiro da fila.
Todo ben, entón se facemos enfileiramento.
Unha vez máis, con calquera de estas estruturas de datos,
xa que estamos lidando con un array, necesitamos comprobar que temos espazo.
>> Este é tipo de como me dicindo vós, se abrir un ficheiro,
ten que comprobar a null.
Con calquera destas pilas e as filas, ten que
a ver se hai espazo porque estamos xestionar unha matriz de tamaño fixo,
como vemos aqui-- 0, 1 todo ata 5.
Entón o que facer nese caso é de selección a ver se aínda temos espazo.
É o noso tamaño inferior a capacidade?
>> Se é así, hai que almacena-lo en a cola e nós actualizamos noso tamaño.
Entón, o que pode ser a cola neste caso?
Non está explicitamente escrita para fóra.
Como podemos almacena-lo?
Cal sería a cola ser?
>> Entón, imos camiñar por este exemplo.
Polo tanto, esta é unha matriz de tamaño 6, non?
E temos agora, o noso tamaño é 5.
E cando nós poñelas, que vai ir ao quinto índice, non?
Así almacenar polo rabo.
>> Outro xeito de escribir cola sería só ser a nosa matriz no índice de tamaño, non?
Isto é de tamaño 5.
A seguinte cousa que vai entrar en cinco.
Legal?
Está ben.
El queda un pouco máis complicado cando comezamos a xogar coa cabeza.
Si?
>> Audiencia: Isto significa que nós declararía unha matriz que
era de cinco elementos de lonxitude e entón nós estamos engadindo a el?
>> COLUMNA 1: Non.
Polo tanto, neste caso, esta é unha pila.
Este sería declarada como unha matriz de tamaño 6.
E neste caso, nós só ten un espazo á esquerda.
>> OK, entón unha cousa é neste caso, se a nosa cabeza está en 0,
entón nós só pode engadir lo en tamaño.
Pero queda un pouco máis complicado porque, en realidade,
Non ten unha foto para iso, entón eu vou
deseñar un porque non é tan sinxelo, xa que
comezar a se librar das cousas.
Así, mentres que cunha pila só ten
preocuparse polo que o tamaño é cando está engadindo algo sobre,
cunha cola que tamén cómpre facer Asegúrese de que a súa cabeza está contabilizado,
porque unha cousa legal sobre filas é que se non está coa súa capacidade,
pode realmente facer iso enrole.
>> OK, entón un coisa-- Oh, iso é terrible giz.
Unha cousa a considerar é o caso.
Nós imos só facer cinco.
OK, entón nós estamos indo a din que a cabeza está aquí.
Este é 0, 1, 2, 3, 4.
>> A cabeza está aí, e por favor, ten cousas en si.
E queremos engadir algo, non?
Entón, o único que necesitamos sabe é que a cabeza é sempre
vai moverse deste xeito e logo volta ao comezo volta, OK?
>> Polo tanto, esta cola ten espazo, non?
Ten espazo en principio, tipo de diante deste.
Entón o que necesitamos facer é nós precisa para calcular a cola.
Se sabe que o seu cabeza non cambiou, cola
é só a súa matriz en o índice do tamaño.
>> Pero, en realidade, se está a usar unha fila, súa cabeza probablemente está a ser actualizado.
Entón o que ten que facer é en realidade calcular a cola.
Entón, o que facemos é esta fórmula aquí, que eu vou deixar
vostedes pensan sobre e entón imos falar sobre iso.
Polo tanto, esta é a capacidade.
>> Entón, iso vai realmente darlle unha forma de facelo.
Porque neste caso, o que?
A nosa cabeza está en 1, o noso tamaño é 4.
Se nós mod que por 5, obtemos 0, que é onde debe introducir-lo.
>> Entón, a continuación, no caso seguinte, se tivésemos que facelo,
podemos dicir, OK, imos desenfileirá algo.
Nós desenfileirá iso.
Tomamos a este elemento, non?
>> E agora a nosa cabeza está a apuntar aquí, e queremos engadir noutra cousa.
Este é basicamente o de atrás da nosa liña, non?
As colas poden involucrar ao redor da matriz.
Esta é unha das principais diferenzas.
Pilas, non pode facelo.
>> Con colas, pode porque todo o que importa
é que sabe o que engadiuse máis recentemente.
Xa que todo vai ser engadido en neste sentido cara á esquerda, no caso en apreciado,
e logo enrole arredor, pode seguir poñendo en novos elementos
na parte de diante da matriz porque non é realmente
diante da matriz máis.
Pode pensar no inicio do matriz como na súa cabeza realmente é.
>> Polo tanto, esta fórmula é como calcular a súa cola.
Será que isto ten sentido?
Está ben.
OK, dequeue, e logo Vostedes teñen 10 minutos
para me preguntar calquera preguntas de aclaración quere, porque sei que é loucura.
>> Todo ben, entón o mesmo maneira-- Non sei se vostedes notaron,
pero CS é todo sobre patróns.
As cousas son moi fermoso o mesmo, só con pequenos axustes.
Entón mesmo aquí.
Necesitamos comprobar a ver se realmente teñen algo na nosa cola, non?
Dicir, OK, é o noso tamaño maior que 0?
Legal.
>> Se o facemos, entón nós nos movemos nosa cabeza, que é o que eu acabo demostrado aquí.
Nós actualizamos a nosa cabeza para ser máis un.
E despois de que nós diminuiremos nosa tamaño e voltar o elemento.
>> Hai moito máis concreto código en study.cs50.net,
e eu recomendo ir por iso, se ten tempo,
aínda que sexa só un pseudo-código.
E se vostedes queren falar a través que comigo un a un, por favor, me deixe
sei.
Eu sería feliz en.
As estruturas de datos, se tomar CS 124, vai
sabemos que as estruturas de datos queda moi diversión e este é só o comezo.
>> Entón, sei que é difícil.
Está certo.
Nós loitamos.
Eu sigo a facer.
Entón non se preocupe moito con iso.
>> Pero iso é basicamente o Crash Course en estruturas de datos.
Sei que é moito.
Hai algo que nós quere ir de novo?
O que quero falar a través?
Si?
>> Audiencia: Para este exemplo, de xeito a cola nova é a 0 sobre iso?
COLUMNA 1: Si.
Audiencia: Aceptar.
Entón pasando, que tería un máis 4 ou-
>> COLUMNA 1: Entón estaba dicindo, cando queremos ir facelo de novo?
Audiencia: Yeah.
Entón, se estaba imaxinando out-- onde están calcular a cola da niso?
>> COLUMNA 1: Entón a cola foi em-- eu mudei iso.
Así, neste exemplo aquí, esta foi a matriz que estamos mirando, OK?
Polo tanto, temos cousas en 1, 2, 3 e 4.
Polo tanto, temos a nosa cabeza é igual a 1 no Neste punto, o tamaño e a é igual a 4
neste punto, non?
>> Vós todos están de acordo que é o caso?
Entón nós facemos a cabeza máis o tamaño, o que dános 5, e entón nós mod por 5.
Recibimos 0, o que nos di que 0 é onde está a nosa cola, onde temos espazo.
>> Audiencia: ¿Que é un cap?
>> COLUMNA 1: A capacidade.
Sentímolo.
Entón ese é o tamaño da súa matriz.
Si?
>> Audiencia: [inaudível] antes devolvemos o elemento?
>> COLUMNA 1: Entón, pasamos a ir ou volver do momento?
Entón, se nós nos movemos un, diminuír o tamaño?
Aguante.
Eu definitivamente esqueceu o outro.
Non importa.
Non hai outra fórmula.
Si, desexa volver a cabeza e, a continuación, movelo de volta.
>> Audiencia: OK, porque neste punto, a cabeza estaba en 0,
e despois quere regresar índice 0 e, a continuación, facer a cabeza 1?
>> COLUMNA 1: Certo.
Eu creo que hai outro tipo fórmula de como esta.
Non teño iso na parte superior da miña cabeza como Non quero darlle a persoa errada.
Pero eu creo que é perfectamente válida para digamos, OK, garde esta element-- o que quere
elemento de cabeza é-- diminuír a súa tamaño, mover a cabeza máis, e retorno
o que quere que ese elemento é.
Isto é perfectamente válido.
Está ben.
Eu sinto que iso non é como o most-- non está
vai saír de aquí como, si, sei intentos.
Teño todo.
Isto está ok.
Eu prometer.
Pero estruturas de datos que son algo hai que moito tempo para se acostumar.
Probablemente unha das máis difíciles cousas, eu creo que, no curso.
>> Por iso, en definitiva leva repetición e mirando at-- I
realmente non sei listas ligadas ata que eu fixen máis con eles,
do mesmo xeito que eu non fixen realmente entender punteiros
ata que eu tiven que ensino-lo para dous anos e fago os meus propios Serie de exercicios con el.
Ten unha morea de reiteración e do tempo.
E, finalmente, que vai tipo de clic.
>> Pero, mentres tanto, se ten o tipo dun elevado nivel de comprensión que
estes fan, os seus pros e que é o que cons--
nós realmente tenden a enfatizar, especialmente no curso de introdución.
Como, por que usaría un intento a través dunha matriz?
Como, cales son os aspectos positivos e negativos de cada un deles?
>> E entender os trade-offs entre cada unha destas estruturas
é o que é moito máis importante agora.
Non pode ser un tolo ou dúas preguntas que se
vai pedirlle para aplicar impulso ou aplicar pop ou enfileiramento e retirar da cola.
Pero, na maior parte, tendo esta maior nivel de comprensión e máis
dunha comprensión intuitiva é máis importante que realmente
poder implementar lo.
>> Sería realmente marabilloso se todos vostedes podía saír e ir aplicar un intento,
pero entendemos que non é necesariamente o máis razoable agora.
Pero pode no seu pset, se quere para, a continuación, vai comezar a práctica,
e logo, quizais realmente entende-la.
Si?
>> Audiencia: OK, entón cales son que pretendía usar no pset?
Necesito usar un deles?
COLUMNA 1: Si.
Entón tes a súa elección.
Creo que, neste caso, podemos falar do pset algo
porque eu execute a través destes.
Así, no seu pset, ten o seu elección de intentos ou táboas de hash.
Algunhas persoas van tentar e utilizar filtros de Bloom,
pero os que tecnicamente non son correctos.
Debido á súa natureza probabilística, eles dan falsos positivos, ás veces.
San ollar frío en, con todo.
Recomendo ollar para eles, polo menos.
Pero ten a súa elección entre unha táboa hash e un intento.
E iso vai ser onde leva no seu dicionario.
>> E terá que escoller súa función de hash,
ten que escoller cantos baldes ten, e vai variar.
Como se ten máis baldes, quizais el vai executar máis rápido.
Pero quizais está perdendo un moito espazo dese xeito, con todo.
Ten que descubrir iso.
Mmhmm?
>> Audiencia: Vostede dixo antes que podemos utilizar outras funcións de hash,
que non temos a crear unha función hash?
>> COLUMNA 1: Si, certo.
Entón, literalmente, para a súa función de hash, como Google "función hash"
e ollar para algúns dos máis interesantes.
Non está prevista a construción súas propias funcións de hash.
As persoas gastan o seu teses sobre estas cousas.
>> Entón non se preocupe sobre a construción do seu propio país.
Buscar unha liña para comezar.
Algúns deles ten que manipular algo
para garantir que tipo de retorno igualar-se e outros enfeites, así, en principio,
Eu recomenda usar algo realmente fácil que quizais só
hashes na primeira letra.
E, a continuación, xa que ten que traballar, incorporando unha función hash máis frío.
Mmhmm?
>> Audiencia: Será que un intente ser ou eficiente, pero só máis difícil, como--
>> COLUMNA 1: Entón unha oportunidade, eu creo, é intuitivamente difícil de aplicar
pero é moi rápido.
Con todo, ocupa máis espazo.
De novo, pode optimizar tanto dos que están no diferentes xeitos e hai formas a--
Audiencia: Como estamos clasificados sobre iso?
Será que matter--
>> COLUMNA 1: Entón está clasificado como normal.
Vai ser graduada en deseño.
Independentemente da forma como fai, quere que seguro que é tan elegante como pode ser
e tan eficiente canto posible.
Pero se escolle un intento ou de hash mesa, con tal de que funciona,
estamos felices con iso.
E se usa algo que hashes na primeira letra, iso é bo,
como é posible que como deseño-wise.
Tamén estamos acadando o punto neste semester--
Non sei se caras noticed-- se está
graos PSet diminuír un pouco debido ao deseño e outros enfeites,
iso é perfectamente normal.
Está quedando a un punto onde a súa programas están ficando cada vez máis complicado.
Hai máis lugares pode mellorar.
>> Por iso é perfectamente normal.
Non é que está facendo peor no seu pset.
É só que estamos sendo máis difícil para vostede agora.
Entón, todo o mundo está sentindo isto.
Eu só graduada todos os seus Serie de exercicios.
Sei que todo o mundo está sentindo isto.
>> Polo tanto, non se preocupe con iso.
E se ten calquera dúbida Serie de exercicios anteriores ou formas que pode mellorar,
Intento e comentar o específico lugares, pero ás veces é tarde
e eu fico canso.
Existen outras cousas sobre estruturas de datos?
Estou seguro de que vostedes realmente non quero falar máis deles,
pero se hai, eu estou feliz de pasar por riba deles, así como calquera cousa
de charla pasado semana ou a semana pasada.
>> Sei que a semana pasada foi toda a revisión, de xeito podemos ter pulado algunha revisión
da charla.
Todas as outras preguntas podo responder?
OK, todo ben.
Ben, vostedes saír 15 minutos máis cedo.
>> Esperamos que este era semi-útil, polo menos, e eu vou ver vostedes a próxima semana,
ou o horario de expediente xoves.
Hai peticións de merendas á seguinte semana, que é a cousa?
Porque eu esquezo de doces hoxe.
E eu trouxo doces última semana, pero era día de Colón,
non eran como seis persoas que tiña catro bolsas de doces para ti.
Podo traer Starbursts novo se queres.
Starbursts?
OK, parece bo.
Ten un gran día, persoal.