>> COLUMNA 1: Todo ben, entón estamos de volta.
Benvido ao CS50.
Isto é o fin de semana sete.
Entón, lembro que a última vez, comezan buscando un pouco máis sofisticado
estruturas de datos.
Xa que, ata agora, todo o que tiña de verdade á nosa disposición era iso, un array.
>> Pero, antes de descartar a matriz como non todo o que interesante, o que de feito
realmente é, o que son algunhas das vantaxes destes datos sinxela
estrutura ata agora?
Que é que é bo?
Ata agora, como vimos?
O que ten?
Nada.
>> Estudante: [inaudível].
>> COLUMNA 1: ¿Que é iso?
>> Estudante: [inaudível].
>> COLUMNA 1: tamaño fixo.
Ok, entón por que é tamaño fixo bo entón?
>> Estudante: [inaudível].
>> COLUMNA 1: OK, polo que é eficiente en a sensación de que pode reservar un
cantidade fixa de espazo, que espero É precisamente tanto
espazo como quere.
Así que podería ser absolutamente unha vantaxe.
>> Cal é o outro lado por un conxunto?
Si?
>> Estudante: [inaudível].
>> COLUMNA 1: Todo o - sorry?
>> Estudante: [inaudível].
>> COLUMNA 1: Todas as caixas na memoria ou á beira do outro.
E iso é útil - por que?
Isto é ben verdade.
Pero como podemos explorar tanto verdade?
>> Estudante: [inaudível].
>> COLUMNA 1: Exactamente, podemos seguir onde todo é só por saber
un enderezo, ou sexa, o enderezo do primeiro byte dese bloque de memoria.
Ou, no caso da cadea, a dirección da primeira
char que cadea.
E a partir de aí, podemos atopar o final da cadea.
Podemos atopar o segundo elemento, o terceiro elemento, e así por diante.
>> E así, a forma elegante de describir que característica é que as matrices darnos
de acceso aleatorio.
Só mediante o corchete notación e un número, pode ir para
un elemento específico da matriz en tempo constante, O gran
dunha, por así dicir.
>> Pero houbo algunhas desvantaxes.
Que unha matriz non facer moi facilmente?
¿Que é iso non é bo?
>> Estudante: [inaudível].
>> COLUMNA 1: ¿Que é iso?
>> Estudante: [inaudível].
>> COLUMNA 1: Expansión de tamaño.
Así, os inconvenientes da matriz son precisamente o contrario do que o
Upside son.
Entón, unha das desvantaxes é que é un tamaño fixo.
Entón non pode realmente crecer.
Podes recolocar unha porción maior memoria e, a continuación, mover os elementos antigos
na nova matriz.
E, entón, libre da vella matriz, para exemplo, utilizando malloc ou similar
función chamada realloc, que realoca memoria.
>> Realloc, como un aparte, intenta darlle memoria que é ao lado da matriz
que xa ten.
Pero pode cambiar as cousas volta por completo.
Pero, en definitiva, que é caro, non?
Porque se ten un bloque de memoria de deste tamaño, pero o que realmente quere un
deste tamaño, e quere conservar os elementos orixinais, ten
preto dun proceso de copia de tempo lineal que debe pasar desde
array antigo para o novo.
E a realidade está pedindo ao funcionamento sistema novo e de novo e
novo para grandes anacos de memoria pode comezar lle custa moito tempo tamén.
Por iso, é tanto unha bendición e unha maldición en disfrazar o feito de que estas matrices
son de tamaño fixo.
Pero se introducir algo no canto así, o que chamamos un linked
lista, recibimos algúns pros e algunhas desvantaxes aquí tamén.
>> Así, unha lista ligada é simplemente un conxunto de datos estrutura composta de estruturas C neste
caso, onde unha struct, aviso, é só un recipiente para unha ou máis específico
tipos de variables.
Neste caso, o que os tipos de datos parecen estar dentro da estrutura que
última vez que chama nó?
Cada un destes rectángulos é un nó.
E cada un dos rectángulos pequenos dentro do que é un tipo de datos.
Cales son os tipos que dixemos estaban o luns?
Si?
>> Estudante: [inaudível].
>> COLUMNA 1: A variable e un punteiro, ou máis especificamente, un int, a n,
e un punteiro no fondo.
Tanto dos que ser 32 bits ás menos nun equipo como este CS50
Appliance, e por iso son igualmente deseñada en tamaño.
>> Entón, o que está a usar o punteiro a pesar de parecer?
Por que engadir esta frecha agora, cando as matrices foron tan agradable e limpo e simple?
Qué é o punteiro facendo por nós en cada un destes nodos?
>> Estudante: [inaudível].
>> COLUMNA 1: Exactamente.
Está dicindo a vostede onde a seguinte é.
Entón eu medio que usar a analoxía de mediante un fío de clasificar de
enfiar eses nós xuntos.
E iso é o que estamos facendo punteiros que cada unha delas
anacos de memoria pode ou non ser contigua, de costas cara atrás
dentro de RAM, xa que cada vez que chamar malloc dicindo, dáme o suficiente
bytes para un novo nodo, que podería estar aquí ou pode ser aquí.
Pode ser aquí.
Vostede simplemente non sabe.
>> Pero o uso de punteiros en enderezos de os nós, pode uni-las
xuntos de maneira que semella visual como unha lista, aínda que esas cousas son
todos espallados por todo o seu un ou seus dous ou os seus catro gigabytes de memoria RAM
dentro do seu propio ordenador.
>> Entón, o lado negativo, entón, de unha lista ligada é o que?
¿Que é un prezo que estamos aparentemente pagando?
>> Estudante: [inaudível].
>> COLUMNA 1: Máis espazo, non?
Temos, neste caso, duplicando a cantidade de espazo, porque nós fomos
desde 32 bits para cada nó, para cada int, agora de 64 bits, porque debemos
manter en torno a un punteiro ben.
Gañou máis eficiencia se o struct é maior que esa cousa sinxela.
Se realmente ten un alumno dentro de que é un par de cordas para
nome e casa, quizais un número de identificación, quizais algúns outros campos completamente.
>> Entón, se ten unha gran estrutura suficiente, quizais o custo do punteiro está
non como un gran negocio.
Isto é un pouco de un caso de esquina no que que estamos almacenando unha simple primitivo como
dentro da lista encadeada.
Pero o punto é o mesmo.
Está definitivamente gastar máis memoria, pero está a recibir
flexibilidade.
Porque agora se eu queira engadir un elemento no inicio da lista,
Teño que reservar un novo nodo.
E eu teño que actualizar os frechas de algunha maneira por só movendo
algúns consellos redor.
>> Se eu queira introducir algo na través da lista, eu non teño a
empurrar todos para o lado como fixemos en pasado semanas cos nosos voluntarios que
representada unha matriz.
Só podo asignar un novo nó e a continuación, pode apuntar as frechas no
diferentes direccións, porque non ten que permanecer no real
memoria dunha liña de verdade como eu deseño aquí na pantalla.
>> E entón, finalmente, se quere inserir algo que, ao final da lista, está
aínda máis fácil.
Esta é unha especie de notación arbitraria, mais punteiro de 34, dar un palpite.
Cal é o valor do seu punteiro máis probable tipo elaborado de como un vello
antena escola alí?
>> Estudante: [inaudível].
>> COLUMNA 1: É probabelmente nulo.
E, de feito, que é un autor representación do nulo.
E é nulo porque é absolutamente Necesitamos saber onde o fin dun linked
lista é, para continuar a seguir e seguindo e seguindo esas frechas
para un valor de lixo.
Entón nulo pode significar que non hai ningunha máis nós á dereita do número 34,
neste caso.
>> Así, propoñemos que podemos aplicar ese nó no código.
E vimos este tipo de sintaxe antes.
Typedef só define un novo tipo de nos, ofrécenos un sinónimo como
cadea era para char *.
Neste caso, vai dar notación abreviada para que nó struct
pode no canto de só ser escrita como nodo, o que é moito máis limpo.
É moito menos detallada.
>> No interior dun nodo é aparentemente un int chamado n, e, a continuación, un nodo struct *
o que significa exactamente o que queriamos que o frechas que dicir, un punteiro a outra
nodo do mesmo tipo de datos exactos.
E eu propoño que podería aplicar un función de busca coma este, que a
primeira vista pode parecer algo complexo.
Pero imos vela no contexto.
>> Déixeme ir ao aparello aquí.
Déixeme abrir un ficheiro chamado lista de cero punto h.
E iso só contén a definición de nós só vin hai pouco a estes datos
tipo chamado un nó.
Entón poñemos isto nun ficheiro h punto.
>> E como un aparte, aínda que esta programa que está a piques de ver é
non todo o que complexo, é de feito convenio cando se escribe un programa para
poñer as cousas como tipos de datos, para tirar constantes, ás veces, dentro do seu
ficheiro de cabeceira, e non necesariamente en o ficheiro C, por suposto cando o seu
programas quedan maiores e máis grandes, de xeito que sabe onde mirar tanto para
documentación, nalgúns casos, ou ao básico como este, os
definición de calquera tipo.
>> Se eu agora abrir lista de cero punto c, teña en conta algunhas cousas.
Inclúe algúns arquivos de cabeceira, a maioría dos de que nós xa vimos antes.
Inclúe o seu propio ficheiro cabeceira.
>> E como un aparte, por que é o dobre citas aquí, en oposición ao ángulo
soportes na liña que Eu destacou alí?
>> Estudante: [inaudível].
>> COLUMNA 1: Si iso é un ficheiro local.
Entón, se é un ficheiro local da súa preferencia aquí na liña 15, por exemplo, pode utilizar
as comiñas dobres no canto dos soportes angulares.
>> Now sexa deste tipo interesante.
Repare que eu teño declarado mundial variable neste programa na liña 18
chamado por primeira vez, a idea é esta é Será un punteiro para o primeiro
nó na miña lista ligada, e eu teño inicializar a nulo, porque eu teño
non asignado calquera real nós aínda.
>> Entón, iso representa, pictoricamente, o que vin hai pouco na imaxe como
ese punteiro na esquina Lado esquerdo.
Entón, agora, que o punteiro non ten unha frecha.
É ao contrario, é simplemente nulo.
Pero el representa o que será o enderezo da primeira real
nodo da lista.
Entón, eu teño aplicado é unha compañía global porque, como verás, todo iso
programa fai na vida é aplicar unha lista ligada para min.
>> Agora eu teño algúns prototipos aquí.
Decidín aplicar recursos como eliminación, inserción, investigación e
travesía -
o último sendo só atravesar a lista, imprimir os seus elementos.
E agora aquí está a miña rutina de inicio.
E non imos gastar moito tempo en estes xa que esta é unha especie de, esperemos
sombreiro vello agora.
>> Vou facer o seguinte, mentres que o usuario coopera.
Entón, eu estou indo para imprimir este menú.
E eu xa formatado como limpa que puiden.
Se o usuario escribe en un, o que significa queren borrar algo.
Se o usuario escribe en dous, o que significa queren introducir algo.
E así sucesivamente.
Vou entón pedir seguida por un comando.
E entón eu vou usar GetInt.
>> Polo tanto, este é un menuing moi sinxelo interface onde só precisa escribir
un mapeamento a un número destes comandos.
E agora eu teño unha chave limpa agradable declaración de que vai conectar
o que o usuario inseriu dentro
E se inseriu un, eu vou chamar borrar e romper.
Se ingresaran dous, eu vou chamar introducir e romper.
>> E agora repare que engada cada destes na mesma liña.
Esta é só unha decisión estilística.
Normalmente, vimos algo como esta.
Pero eu decidimos, francamente, o meu programa parecía máis lexible por
tiña só catro casos para só lista-la así.
Uso totalmente lexítimo do estilo.
E eu vou facelo, sempre que o usuario non teña ingresaran cero, o que me
decidiu significará que queren deixar de fumar.
>> Entón agora entender o que estou imos facer aquí.
Vou liberar a lista aparentemente.
Pero máis sobre iso aquí a pouco.
Imos primeiro executar este programa.
Entón deixe-me facer unha terminal máis grande fiestra, punto barra lista 0.
Eu estou indo a ir adiante e poña por dato dous, un número similar de 50, e agora
Vostede verá a lista é agora 50.
E o meu texto só rolou para arriba un pouco.
Entón agora teña en conta a lista contén o número 50.
>> Imos facer outra inserción, tomando dous.
Imos escribir o número como un.
Lista é agora un, seguido por 50.
Polo tanto, esta é só unha representación textual da lista.
E imos introducir un número como o número 42, que é esperanza
vai acabar no medio porque este programa en particular tipo que
elementos, xa que os insere.
Polo tanto, non temos.
Super programa sinxelo que podería absolutamente usar un array, pero eu
ocorrer de estar a usar unha lista encadeada só así podo dinámica
crecer e reduci-lo.
>> Entón, imos dar un ollo para a investigación, se eu mando de tres executar, quero buscar
para, por exemplo, o número 43.
E nada se atopou, ao parecer, porque volvín sen resposta.
Entón, imos facelo de novo.
Buscar.
Imos buscar a 50, ou mellor, procurar a 42, que ten unha fermosa
pouco significado sutil.
E descubrín o significado da vida alí.
Número 42, se non sabe a referencia en Google.
Todo ben.
Entón, o que este programa fixo por min?
É só me permitiu introducir así lonxe e busca de elementos.
>> Imos avanzar, entón, para que a función que mirou
o luns como un teaser.
Entón esa función, eu afirmo, as investigacións para un elemento na lista por primeira
un, alertando o usuario e, a continuación, chamar GetInt para obter un int real
que quere buscar.
>> Entón observe iso.
Eu estou indo para crear unha variable temporal na liña 188 chamado punteiro -
PTR -
podería telo chamado calquera cousa.
E é un punteiro para un nó por que eu dixen no * alí.
E estou inicializar a ser igual primeiro, para que eu efectivamente teño o meu
dedo, por así dicir, no mesmo primeiro elemento da lista.
Entón, se a miña man dereita aquí é PTR eu son apuntando para o mesmo que o primeiro
está a apuntar.
>> Entón, agora de volta o código, o que pasa a continuación -
este é un paradigma común cando a iteración ao longo dunha estrutura como unha
lista ligada.
Vou facer o seguinte, mentres punteiro non é igual a null Así, mentres
meu dedo non está apuntado nalgún nulo valor, se punteiro de frecha n é igual a n.
Imos observar primeiro que non é o que o usuario inseriu por GetInts chamar aquí.
>> E punteiro de frecha n significa o que?
Ben, se nós voltar a imaxe aquí, se eu tivera un dedo apuntando para
que o primeiro nodo que contén nove, o frecha esencialmente significa ir a aquela
nó e pegar o valor na posición n, neste caso, o campo de datos chamado n.
>> Como un aparte - e vimos que algunhas de semanas, cando alguén preguntou -
esta sintaxe é novo, pero non darnos poderes que
xa non ten.
Cal foi esta frase equivalente a usar notación de punto e protagonista dunha parella
de semanas, cando tirada atrás esta capa algo prematuramente?
>> Estudante: [inaudível].
>> COLUMNA 1: Exactamente, foi estrela, e logo foi protagonista punto n, con
parénteses aquí, o que parece, francamente, creo que unha morea
máis enigmática de ler.
Pero a estrela do punteiro, como sempre, medios para alí.
E unha vez que está alí, que datos campo que queres acceder?
Ben, usa a notación de punto para acceder un campo de datos estruturas, e eu
quere especificamente n.
>> Francamente, eu diría que este é só máis difícil de ler.
É máis difícil lembrar de onde que os parénteses ir, o
estrela e todo iso.
Así, o mundo adoptaron algún sintática azucre, por así dicir.
Só unha forma sexy de dicir: isto equivale, e
quizais máis intuitiva.
O punteiro é de feito un punteiro, o frecha significa notación ir alí e atopar
o campo neste caso chamado n.
>> Entón, se eu atopalo, entender o que fago.
Eu simplemente impresión, penso por cento i, conectar o valor para que int.
Eu chamo de durmir por un segundo só para tipo de pausa cousas na pantalla para
dar ao usuario un segundo para absorber o que pasou.
E entón eu gorgolexo.
Se non, o que fago?
Eu actualizar punteiro a igual frecha de punteiro próximo.
>> Entón, só para deixar claro, isto significa ir alí, utilizando o meu notación old-school.
Entón, iso significa só ir a calquera está apuntando para que, o moi
primeiro caso é que eu estou apuntando para a estrutura con nove nel.
Entón eu fun alí.
E entón a notación de punto significa, obter o valor na próxima.
>> Pero o valor, aínda que está deseñado como un estreito, é só un número.
É un enderezo numérico.
Así, esta liña de código, se escrito como este, o máis enigmático
forma, ou así, a pouco máis xeito intuitivo, só significa mover a man
desde o primeiro nodo ao seguinte, e logo, o seguinte, e entón a
seguinte, e así por diante.
>> Polo tanto, non vou me debruzouse sobre a outra implementacións de inserción e exclusión
e transversal, os dous primeiros que son moi implicado.
E eu creo que é moi fácil obter perdido cando facelo verbalmente.
Pero o que podemos facer aquí é tentar determinar como
mellor facelo visualmente.
Porque eu estaba a propoñer que se quere inserir elementos para esa
lista existente, o que ten cinco elementos -
9, 17, 22, 26 e 33 -
se eu estivese indo a aplicar iso en código, eu teño considerar como ir
sobre como facelo.
>> E gustaríame propoñer a dar pasos de bebé segundo a cal, neste caso, é dicir, cales son
os escenarios posibles que pode atopar en xeral?
Ao aplicar inserción dun linked lista, iso só pasa de ser un
exemplo específico de tamaño cinco.
Ben, se quere inserir un número, como diría o número un, e
mantemento da orde clasificada, onde Obviamente acontece co número un ten
ir neste exemplo específico?
Igual no inicio.
>> Pero o que é interesante alí é que Se desexa inserir unha nesa
lista, o punteiro necesidades especiais actualizarse parecer?
First.
Entón, eu diría, este é o primeiro caso que pode querer considerar un
escenario que implica a inserción no o inicio da lista.
>> Imos arrincar fóra quizais unha tan fácil ou mesmo caso máis sinxelo, en concepto falando.
Supoña que queira inserir a número 35 en orde de clasificación.
É, obviamente, pertence alí.
Entón, o punteiro obviamente vai Ten que ser actualizado nese escenario?
Punteiro de 34 polo que non nulo pero a dirección da estrutura
contén o número 35.
Entón, iso é caso dous.
Entón, xa, eu son unha especie de cuantización a cantidade de traballo que teño que facer aquí.
>> E, finalmente, no caso do medio é obvio de feito, no medio, se eu queira
introducir algo así como dicir 23, que vai entre os 23 e os 26, pero
Agora as cousas están un pouco máis parte, porque o que
punteiros precisa ser cambiado?
Entón, 22 obviamente precisa ser cambiado porque non pode apuntar máis de 26.
El que apuntar para o novo nodo Vou ter que reservar chamando
malloc ou algún equivalente.
>> Pero, entón, eu tamén teño o novo nodo, 23 neste caso, que o seu punteiro
apuntando para quen?
26.
E aí, será unha orde das operacións aquí.
Porque se eu fai iso locamente, e eu por exemplo, no inicio do comezo
da lista, e meu obxectivo é introducir 23.
E eu comprobar, pertence aquí, preto de nove?
Non
Será que é aquí, xunto con 17?
Non
Será que pertence aquí xunto a 22?
Si
>> Agora, se eu son tolo aquí, e non a pensar sobre iso, eu podería
reservar meu novo nodo a 23.
Podo actualizar o punteiro do o no chamado 22, apuntando
en que o novo nodo.
E entón o que eu teño que actualizar punteiro do novo nodo a ser?
>> Estudante: [inaudível].
>> COLUMNA 1: Exactamente.
Apuntando a 26.
Pero caramba, se eu xa non actualizar Punteiro de 22 para apuntar a este cara, e
agora eu teño orfos, o resto da lista, por así dicir.
Así, a orde das operacións aquí será importante.
>> Para iso eu podería roubar, digamos, seis voluntarios.
E imos ver se a xente non pode facelo visual en vez de código-wise.
E temos algúns encantador estrés bolas para ti hoxe.
OK, como sobre un, dous, no de volta - a finais alí.
tres, catro, tanto de ti caras na final.
E, cinco, seis.
Claro.
Cinco e seis.
Todo ben e nós viremos para vós a próxima vez.
Todo ben, imos para arriba.
>> Todo ben, sempre que está aquí en primeiro lugar, quere ser o único xeito
no vidro Google aquí?
Todo ben, entón, OK, Vidro, gravar un vídeo.
OK, está listo para ir.
>> Todo ben, entón se vostedes poden vir aquí, eu preparei con antelación
algúns números.
Todo ben, veña ata aquí.
E por que non ir un pouco aínda máis desta forma.
E imos ver, cal é o seu nome, co vidro Google?
>> ALUMNO: Ben.
>> COLUMNA 1: Ben?
OK, Ben, vai ser a primeira, literalmente.
Por iso, imos enviar-lle cara ao final da etapa.
Todo ben, eo seu nome?
>> ALUMNO: Jason.
>> COLUMNA 1: Jason, OK vai ser o número nove.
Entón, se quere seguir Ben desa forma.
>> ALUMNO: Jill.
>> COLUMNA 1: Jill, está indo a ser 17, que se eu fixese iso máis
intelixente, eu tería iniciado na outra extrema.
Ir por ese camiño.
22.
E vostede é?
>> ALUMNO: Mary.
>> COLUMNA 1: Mary, vai ser 22.
E o seu nome é?
>> ALUMNO: Chris.
>> COLUMNA 1: Chris, vai ser 26.
E entón, finalmente.
>> ALUMNO: Diana.
>> COLUMNA 1: Diana, vai ser 34.
Entón vén aquí.
>> Todo ben, tan perfecto clasificadas encargar xa.
E imos adiante e facelo para que poidamos realmente -
Ben é só o tipo de busca fóra en nada alí.
OK, entón imos seguir adiante e describir esta usando armas, así como eu era, exactamente,
o que está pasando.
Entón vai adiante e dar-vos un pé ou dous entre vós.
E vai adiante e apuntar cunha man para quen ten que estar apuntando para
derivada.
E se é nula só apuntar directo para o chan.
OK, todo ben.
>> Polo tanto, agora temos unha lista ligada, e déixeme propoñer que vou desempeñar o papel
PTR, entón eu non vou incomodar tendo esta ao redor.
E entón - alguén convención estúpida - pode chamar iso de calquera cousa que quere -
punteiro predecesor, punteiro pred -
é só o apelido que demos en noso código de exemplo para a man esquerda.
O outro lado, que será manter o control de quen é quen no
seguintes escenarios.
>> Entón supoño que, en primeiro lugar, quero arrincar fóra aquel primeiro exemplo de inserción de, digamos
20, na lista.
Entón, eu vou ter que alguén para encarnan o número 20 para nós.
Entón eu teño de alguén para malloc do público.
Imos para arriba.
Cal é o seu nome?
>> ALUMNO: Brian.
>> COLUMNA 1: Brian, todo ben, entón debe ser o nodo que contén 20.
Todo ben, veña ata aquí.
E, obviamente, onde Brian non pertence?
Así, no medio - en realidade, agarde un minuto.
Estamos facendo isto para fóra de orde.
Estamos facendo iso moito máis difícil do que el ten que estar en primeiro lugar.
OK, imos libre Brian e realloc Brian cinco.
>> OK, entón agora queremos introducir Brian como cinco.
Entón veña aquí xunto Ben só por un momento.
E pode dicir presuntamente onde esta historia vai dar.
Pero imos pensar coidadosamente sobre a orde das operacións.
E é precisamente esta visuais que vai aliñar
con ese código de mostra.
Entón, aquí eu PTR apuntando inicialmente non en Ben, por si só, pero en calquera
valor que contén, o que neste caso é - cal é o seu nome?
>> ALUMNO: Jason.
>> COLUMNA 1: Jason, entón Ben e eu somos apuntando a Jason neste momento.
Entón agora eu teño de determinar, onde é que Brian pertence?
Entón o único que eu teño acceso a agora é o elemento de datos n.
Entón eu vou dar un ollo, é Brian menos Jason?
A resposta é verdadeira.
>> Entón, o que ten agora de pasar, na orde correcta?
Necesito actualizar cantos punteiros en total nesta historia?
Onde a man aínda está a apuntar cara Jason, e súa man - se quere
poñer a man como, de algunha maneira, eu Non sei, un punto de interrogación.
OK, bo.
>> Todo ben, así que ten algúns candidatos.
Ou Ben ou eu ou Brian ou Jason ou calquera outra persoa, que
punteiros que cambiar?
Cantos en total?
>> OK, entón dous.
O meu punteiro realmente non importa máis porque eu son só temporal.
Por iso, é estes dúas caras, presumiblemente, Ben e Brian.
Entón deixe-me propor que nós actualizamos Ben, xa que está en primeiro lugar.
O primeiro elemento da lista agora será Brian.
Así punto Ben en Brian.
OK, e agora?
>> Quen está apuntada para quen?
>> Estudante: [inaudível].
>> COLUMNA 1: OK, entón Brian ten para ligar a Jason.
Pero o que eu perdín a noción do que punteiro?
Non sei onde Jason é?
>> Estudante: [inaudível].
>> COLUMNA 1: fago, sempre que eu son o punteiro temporal.
E, presuntamente, non cambiei para apuntar para o novo nodo.
Así, podemos simplemente ter punto de Brian en quen estou apuntando.
E estamos a facer.
Así, un caso, a inserción na inicio da lista.
Había dous pasos fundamentais.
Un deles, temos que actualizar Ben, e, a continuación, Tamén temos que actualizar Brian.
E entón eu non ten que se preocupar deambulan polo resto da
lista, porque xa atopou o seu localización, porque pertencía ao
esquerda do primeiro elemento.
>> Todo ben, entón moi sinxelo.
De feito, parece que estamos case facendo iso moi complicado.
Entón, imos agora arrincar fóra da final da lista, e ver onde
a complexidade comeza.
Entón, se agora distribución do público.
Calquera quere xogar 55?
Todo ben, eu vin o de primeira man.
Imos para arriba.
Si
Cal é o seu nome?
>> Estudante: [inaudível].
>> COLUMNA 1: Habata.
Ok, imos alí enriba.
Vai ser o número 55.
Entón, por suposto, pertencen ó final da lista.
Entón, imos repetir a simulación comigo sendo o PTR só por un momento.
Entón, eu estou indo primeiro para ligar o que Ben está a apuntar.
Nós dous estamos apuntando agora en Brian.
Así, 55 non é menos que cinco.
Entón eu vou actualizar por apuntando ao seguinte punteiro de Brian, que
agora é, por suposto, Jason.
55 non sexa inferior a nove, de xeito Vou actualizar PTR.
Vou actualizar PTR Vou actualizar PTR.
E eu vou - hmm, o que é o seu nome?
>> ALUMNO: Diana.
>> COLUMNA 1: Diana está apuntando, por suposto, o nulo coa man esquerda.
Entón onde é que realmente Habata pertencen claramente?
Á esquerda, aquí.
Entón, como é que eu sei para poñelo aquí Eu creo que eu estraguei todo.
Porque o que é PTR arte neste momento?
Nulo.
Así, aínda que, visualmente, o que pudermos ver, obviamente, todo isto
caras aquí no escenario.
Non teño mantido a par do anterior persoa da lista.
Non teño un dedo apuntando cara fóra, neste caso, o número de nodo 34.
>> Entón, imos comezar esta remate.
Entón, agora eu realmente teño unha segunda variable local.
E iso é o que podes ver no código C mostra real, onde, como eu vou,
cando eu actualizar a miña man dereita para ligar Jason, deixando, así, Brian atrás, eu
mellor comezar a usar a man esquerda actualizar onde eu estaba, para que, como eu vou
a través desta lista -
máis sen xeito do que eu pretendía agora aquí visual -
Vou chegar ao final da lista.
>> Esta man aínda é nulo, o que é moi inútil, excepto para indicar
Son claramente ao final da lista pero agora polo menos eu teño esa
punteiro predecesor apuntar aquí, entón agora que as mans e os punteiros que debe
para ser actualizado?
Cuxa man que quere reconfigurar primeiro?
>> Estudante: [inaudível].
>> COLUMNA 1: OK, entón Diana.
Onde quere apuntar Punteiro á esquerda de Diana at?
Aos 55 anos, presume-se, de xeito que temos inserido alí.
E onde deben ir 55 punteiro?
Abaixo, representando nulo.
E as mans, neste momento, non importa, porque eran só
variables temporais.
Polo tanto, agora estamos a facer.
>> Así, a complexidade adicional alí - e non é tan difícil de aplicar,
pero precisamos dunha variable secundaria para facer seguro de que antes de cambiar a miña dereita
banda, eu actualizar o valor do meu lado esquerdo banda, o punteiro pred neste caso, de xeito
que eu teño un punteiro de arrastre manter o control de onde eu estaba.
Agora, como un aparte, se está a pensar que iso través, este se sente como se fose un
pouco aburrido ter que manter seguir desa man esquerda.
>> Cal sería outra solución a este problema foron?
Se ten que redeseñar os datos estrutura que estamos a falar
por agora?
Se este tipo de só se sente un pouco aburrido ter, tipo, dous punteiros
pasando a lista, quen máis podería ter, nun mundo ideal, mantense
información de que necesitamos?
Si?
>> Estudante: [inaudível].
>> COLUMNA 1: Exactamente.
Dereito así que non hai realmente unha interesante xerme de unha idea.
E esta idea dun punteiro anterior, apuntando para o elemento anterior.
E se eu só incorporada que dentro da propia lista?
E iso vai ser difícil de ver iso sen todo o papel
caendo no chan.
Pero supoña que estes faces usado tanto das súas mans a unha previa
punteiro, e un punteiro próximo, así aplicar o que imos chamar un dobre
lista ligada.
Iso me permitiría clasificar de rewind, moito máis facilmente, sen min, o
programador, ter que manter controlar manualmente -
verdadeiramente a man -
de onde eu fora anteriormente na lista.
Polo tanto, non imos facelo.
Imos mantelo simple, porque iso é terá un prezo, dúas veces máis
moito máis espazo para os punteiros, se quere un segundo.
Pero isto é de feito un común estrutura de datos coñecida como un
lista dobremente ligada.
>> Imos facer o último exemplo aquí e poñer estes faces fóra da súa miseria.
Entón malloc 20.
Imos superior do corredor alí.
Todo ben, cal é o seu nome?
>> Estudante: [inaudível].
>> COLUMNA 1: Sentímolo?
>> Estudante: [inaudível].
>> COLUMNA 1: Demeron?
OK imos alí cara arriba.
Ten que ser 20.
Vostede, obviamente, vai pertencer entre 17 e 22.
Entón me deixe aprender a lección.
Vou comezar punteiro apuntando a Brian.
E eu vou ter a miña man esquerda só actualizar a Brian como eu pasar para
Jason, comprobación fai 20 a menos que nove?
Non
É de 20 a menos de 17 anos?
Non
É de 20 a menos de 22?
Si
Entón, o que os punteiros ou mans que cambiar onde están a apuntar agora?
>> Así, podemos facer 17 apuntando a 20.
Entón, iso é bo.
Onde queremos apuntar o punteiro agora?
Aos 22 anos.
E sabemos que 22 é, unha vez máis, grazas ao meu punteiro temporal.
Entón, nós estamos OK alí.
Así, debido a este almacenamento temporal Eu mantiven o control de onde todo o mundo é.
E agora pode ir a onde visual vostede pertence, e agora necesitamos 1, 2, 3,
4, 5, 6, 7, 8, 9 bolas de estrés, e unha salva de palmas para
estes faces, se puidésemos.
Ben feito.
>> [Aplausos]
>> COLUMNA 1: Todo ben.
E pode manter as pezas mementos papel.
>> Todo ben, entón, confíe en min é moi máis fácil entrar por aquela con
os seres humanos do que con código real.
Pero o que vai atopar nun momento agora, é o mesmo - Oh, moitas grazas.
Grazas -
é que vai descubrir que os mesmos datos estrutura, unha lista ligada, realmente pode
ser utilizado como un bloque de construción aínda máis estruturas de datos sofisticadas.
>> E entender tamén o tema aquí é que temos absolutamente introduciu máis
complexidade na implantación deste algoritmo.
Inserción, e pasou por iso, exclusión e consulta, é algo
máis complicado do que Foi con unha matriz.
Pero gañar un dinamismo.
Temos unha estrutura de datos adaptativa.
>> Pero, de novo, nós pagamos un prezo de ter algún complexidade adicional, tanto en
implementar lo.
E estamos desistido de acceso aleatorio.
E para ser honesto, non hai algún bo borrar diapositivas podo dar-lle que
Di aquí que é por iso que unha lista ligada é mellor que unha matriz.
E deixar por iso mesmo.
Porque o tema recurrente agora, aínda máis aínda nas próximas semanas, é
que non é necesariamente unha resposta correcta.
>> É por iso que temos o eixe separado do proxecto para conxuntos de problemas.
Vai ser moi sensible ao contexto Se quere usar estes datos
estrutura ou aquel, e vai depende do que é importante para vostede en termos
de recursos e complexidade.
>> Pero déixeme propoñer que os datos ideais estrutura, o Santo Graal, sería
algo que é constante de tempo, independentemente da cantidade de material
dentro del, non sería sorprendente se un estrutura de datos devolveu respostas
tempo constante.
Si
Esta palabra está na súa enorme dicionario.
Ou non, esta palabra non é.
Ou calquera problema deste tipo alá.
Ben, imos ver se non podemos, polo menos, dar un paso cara a iso.
>> Déixeme propor unha nova estrutura de datos que se pode usar para diferentes cousas,
neste caso denominada táboa hash.
E por iso estamos realmente mirando cara atrás nunha matriz, no caso en apreciado, e
arbitrariamente, eu deseño esta táboa hash como unha matriz cunha especie de
matriz bidimensional -
ou mellor, que se describe aquí como un dous matriz dimensional - pero este é só
unha matriz de tamaño 26, de tal xeito que se chamar a táboa da matriz, soporte de mesa
cero é o rectángulo na parte superior.
Táboa soporte 25 é o rectángulo na parte inferior.
E é así que eu podería chamar un conxunto de datos estrutura en que desexa almacenar
nomes de persoas.
>> Así, por exemplo, e eu non vou chamar a cousa toda aquí no alto, se eu
tiña esa matriz, que eu estou indo agora para chamar a unha táboa hash, e este é de novo
Lugar de cero.
Este aquí é a situación un, e así por diante.
Eu afirmo que quero usar estes datos estrutura, por mor da discusión,
para gardar os nomes das persoas, Alicia e Bob e Charlie e outros nomes.
Entón, pense nisto agora, como o inicio de, digamos, un dicionario
con moitas palabras.
Elas acontecen a ser nomes No noso exemplo aquí.
E todo isto é moi pertinente, quizais, para implantación dun corrector ortográfico, como
quizais para o problema de definir seis.
>> Entón, se temos unha matriz de tamaño 26 de xeito que este é o lugar 25
na parte inferior, e eu afirmo que Alicia é a primeira palabra no dicionario de
nomes que quero introducir na RAM, a esta estrutura de datos, onde están
instintos dicindo que Alicia nome debe ir neste array?
>> Temos 26 opcións.
Onde queremos colocar-la?
Queremos que o soporte cero, non?
Un para Alice, imos chamar iso de cero.
E B será un, e C será de dous.
Entón, imos escribir Nome aquí enriba de Alicia.
Se, entón, introducir Bob, o seu nome vai aquí.
Charlie vai pasar aquí.
E así por diante ao longo esta estrutura de datos.
>> Trátase dunha estrutura de datos marabilloso.
Por que?
Ben, o que é o tempo de execución introducir o nome dun humano a esta
estrutura de datos agora?
Dado que esta táboa é aplicado, verdadeiramente, como unha matriz.
Ben, é tempo constante.
É fin dun.
Por que?
>> Ben, como determina onde Alicia pertence?
Mira para que letra do seu nome?
A primeira.
E pode chegar alí, se é unha cadea, só mirando para cadea
Soporte de cero.
Así, o carácter zeroth da cadea.
Iso é doado.
Fixemos iso no Crypto semanas de asignación atrás.
E entón cando vostede sabe que Alicia A carta é a capital, podemos restar
off 65 ou maiúscula si, que nos dá cero.
Así, sabemos que Alicia pertence na posición cero.
>> E dado un punteiro a estes datos estrutura, dalgunha sorte, o tempo fai
el me levar para atopar a localización cero nun array?
Só un paso, non é hora constante debido a que o acceso aleatorio
proposto foi unha característica dunha matriz.
Así, en breve, descubrir o que o índice do nome de Alicia é, que é, en
Neste caso é A, ou imos só resolver que a cero, en que B é un C e é
dous, imaxinando que fora É tempo constante.
Eu só teño que mirar para a súa primeira carta, descubrir onde cero é un
matriz tamén é de tempo constante.
Entón, tecnicamente iso é como dous pasos agora.
Pero iso aínda é constante.
Entón, chamamos iso dun gran A, entón nós Alicia inserida nesta táboa
tempo constante.
>> Pero, por suposto, eu estou sendo inxenuo aquí, non?
E se hai unha Aaron na clase?
Ou Alicia?
Ou outros nomes comezando con A. Onde imos poñer
esa persoa, non?
Quero dicir, agora hai só tres persoas sobre a mesa, entón quizais nós
debe poñer Aaron no lugar cero un, dous, tres.
>> Certo, eu podería poñer un aquí.
Pero entón, se intentamos introducir David en Nesta lista, onde é que David ir?
Agora o noso sistema comeza a romper abaixo, non?
Porque agora David acaba aquí Aaron se é realmente aquí.
E agora toda esa idea de ter un estrutura de datos limpo que nos dá
insercións de tempo constantes, non está constante de tempo, porque eu teño que
comprobar, oh, drogas, alguén xa está no lugar de Alicia.
>> Déixeme investigar o resto dos datos estrutura, a buscar un lugar para poñer
alguén como o nome de Aaron.
E así que tamén está empezando ter tempo lineal.
Ademais, se agora quere atopar o Aaron nesta estrutura de datos, e
comproba, eo nome de Aaron non está aquí.
Ideal, vostede tería só que dicir Arão non na estrutura de datos.
Pero se comezar a facer sala para Aaron onde debería haber un D
ou un E, ti, o peor caso, ten que comprobar Toda a estrutura de datos, en
caso en que se transforma en algo lineal no tamaño da táboa.
>> Entón todo ben, eu vou solucionar isto.
O problema aquí é que eu tiña 26 elementos nesta matriz.
Deixe me cambiar.
Berros.
Déixeme cambiar isto para que, no canto de ser tamaño 26 en total, teña en conta o fondo
índice cambiará de n menos 1.
Si 26 é claramente demasiado pequeno para os seres humanos ' nomes, porque hai miles de
nomes do mundo, imos facer en 100 ou 1000 ou 10000.
Nós só reservar máis espazo.
>> Ben, iso non significa necesariamente diminuír a probabilidade de que non terá dous
persoas con nomes que comezan con A, e así, estaba indo para tratar de poñer un
nomes en lugar aínda a cero.
Eles aínda van chocar, o que quere dicir que aínda que de unha solución para poñer
Alicia e Arão e Alicia e outros nomes que comezan con A en outro lugar.
Pero como un gran problema é ese?
Cal é a probabilidade de que ten colisións nunha base de datos
estrutura como esta?
>> Ben, deixe-me - nós imos volver a esta pregunta aquí.
E mira como poderiamos resolver-lo por primeira vez.
Déixame sacar esta proposta aquí.
O que acabamos de describir é un algoritmo, a heurística chamado lineal
enquisa segundo a cal, se intentou introducir algo aquí nestes datos
estrutura, o que é denominado táboa hash e non hai espazo alí,
verdadeiramente sondar a estrutura de datos verificación, e está dispoñible?
É esta dispoñible e está dispoñible?
É esta dispoñible?
E cando finalmente sexa, inserir a nome que orixinalmente planificado
noutro lugar naquel local.
Pero, no peor dos casos, o único punto pode ser a parte inferior dos datos
estrutura, a fin do array.
>> Entón lineal enquisa, no peor caso, transforma nun algoritmo lineal en que
Arão, se el pasa a ser inserido último neste tipo de estrutura de datos, pode
chocar con esta primeira posición, pero despois acaban por mala sorte na final.
Polo tanto, esta non é unha constante tempo Santo Graal para nós.
Esta visión para a inserción de elementos unha estrutura de datos, chamado de hash
táboa non parecen ser de tempo constante polo menos, no caso xeral.
Pode transformarse en algo lineal.
>> Entón, o que se resolver conflitos un pouco diferente?
Entón aquí vai un máis sofisticado visión para o que é aínda
chamada de táboa de hash.
E, de hash, como un aparte, o que Quero dicir, é o índice que
Me referín anteriormente.
Para hash de algo pode ser pensada como un verbo.
>> Entón, se haxix Alicia é un nome, unha función de hash, por así dicir,
debe devolver un número.
Neste caso será cero a ela pertence localización cero, un, se pertence a
un lugar, e así por diante.
Así, a miña función de hash, ata agora, foi super sinxelo, só mirando para o
primeira letra do nome de alguén.
Pero unha función hash ten como entrada de algún anaco de datos, un
cadea, un int, o que quere.
E el cospe tipicamente un número.
E ese número é o lugar onde os datos elemento pertence a unha estrutura de datos
coñecido aquí como unha táboa hash.
>> Entón, só intuitivamente, esta é unha contexto lixeiramente diferente.
Isto, en realidade estase referindo a un exemplo inclúen aniversarios, cando
pode haber tantos como 31 días no mes.
Pero o que a persoa decide facer en caso dunha colisión?
Contexto agora a ser, non unha colisión de nomes, pero unha colisión de aniversarios,
se dúas persoas teñen a mesma data de aniversario o a 02 de outubro, por exemplo.
>> Estudante: [inaudível].
>> COLUMNA 1: Si, polo que temos aquí a alavancagem de listas ligadas.
Polo tanto, parece un pouco diferente do que chamou máis cedo.
Pero parece que unha matriz na parte esquerda.
Este é un índice, pois ningunha razón particular.
Senón que é un array.
É unha matriz de punteiros.
E cada un deses elementos, cada un de eses círculos ou barras - a barra
representando nula - cada unha delas punteiros é aparentemente apunta a
que a estrutura de datos?
Unha lista ligada.
>> Polo tanto, agora temos a capacidade de codificar no noso programa
o tamaño da táboa.
Neste caso, sabemos que nunca hai máis de 31 días nun mes.
Tan difícil codificación dun valor como 31 é razoable nese contexto.
No contexto de nomes, codificación dura 26 non é razoable que a xente
nomes comezan só con, por exemplo, alfabeto da a Z. inclúen
>> Podemos meter-los todos en que os datos estrutura, sempre que, cando temos un
colisión, non poñer os nomes aquí, no canto de pensar que esas células
como non propias cordas, pero como punteiros para, por exemplo, Alice.
E entón Alicia pode ter outro punteiro a outro nome comezando con
A. E Bob realmente pasa por aquí.
>> E se hai outro nome que comeza con B, el acaba por aquí.
E así, cada un dos elementos do presente mesa de dous, se nos proxectos este un
pouco máis intelixente -
Imos -
se nos proxectos este un pouco máis intelixentemente, torna-se agora un conxunto de datos de adaptación
estrutura, onde non hai límite duro en cantos elementos pode introducir
para el, xa que se ten unha colisión, iso é bo.
Só tes que ir adiante e anexo-lo ao o que vimos un pouco atrás era
coñecido como unha lista ligada.
>> Ben, imos deixar por un momento.
Cal é a probabilidade dunha colisión en primeiro lugar?
Seguro, quizais eu estou máis a pensar, se cadra Estou sobre enxeñaría este problema,
porque vostede sabe o que?
Si, podo vir enriba con arbitrario exemplos enriba da miña cabeza, como
Allison e Aaron, pero, en realidade, dada unha distribución uniforme do
insumos, ou sexa unhas insercións aleatorias nunha estrutura de datos, o que é realmente
a probabilidade dunha colisión?
Ben ve, é realmente super alta.
Déixeme xeneralizar este este problema é como.
>> Así, nunha sala de n CS50 estudantes, o que é a probabilidade de que polo menos
dous alumnos na sala teñen a mesma data de aniversario?
Polo tanto, non hai o que. algúns Hund -
200, 300 persoas aquí e varios centos de persoas na casa hoxe.
Entón, se quería preguntar a nós mesmos o que é a probabilidade de que dúas persoas
nesta sala que ten o mesmo aniversario, podemos descubrir iso.
E eu afirmo en realidade, hai dous persoas co mesmo aniversario.
>> Por exemplo, alguén ten aniversario hoxe?
Onte?
Mañá?
Todo ben, entón parece que vou ter que facer isto máis ou menos 363
veces para realmente descubrir o se temos unha colisión.
Ou podemos facelo matemáticamente ao contrario de tediosamente
facelo.
E propoñer o seguinte.
>> Así, propoño que podería modelar o probabilidade de dúas persoas que teñen a
mesma data de aniversario como a probabilidade dun menos a probabilidade de non ter un
aniversario o mesmo día.
Entón, para conseguir isto, e este é só o xeito elegante de escribir isto, ao
primeira persoa na sala, el ou ela pode ter calquera dos posibles
aniversarios asumindo 365 días o ano, con perdón ás persoas con
o 29 º aniversario de febreiro.
>> Así, a primeira persoa nesta sala é libre ter calquera número de aniversarios
fóra das 365 posibilidades para que imos facer que 365 dividido por 365,
, Que é un.
A seguinte persoa na sala, se o obxectivo é evitar unha colisión, só pode
ter o seu aniversario en como distintos días posibles?
364.
Así, o segundo termo da expresión é esta esencialmente, facendo que a matemática para nós
subtraindo-se fóra dun día posible.
E despois, o día seguinte, o día seguinte, o día seguinte ata o número total
de persoas na sala.
>> E se entón considerar, cal é entón a probabilidade de non ter todo
aniversarios únicas, pero de novo un menos que, o que temos é unha expresión
que pode moi fantasiosamente semellante a esta.
Pero é máis interesante ollar visualmente.
Este é un gráfico no que o eixo x é o número de persoas na sala, o
número de aniversarios.
No eixe y representa a probabilidade dunha colisión, dúas persoas
tendo o mesmo aniversario.
>> E o takeaway dende esta curva é que, así que comeza a gustar 40
estudantes, estase a unha probabilidade do 90% combinatorically de dous
ou máis persoas que teñen aniversario o mesmo día.
E unha vez que comeza a gustar de 58 persoas é preto de 100% de unha posibilidade ambos
persoas na sala terá o mesma data de aniversario, aínda que non haxa
365 ou 366 posibles baldes e só 58 persoas na sala.
Só estatisticamente é probable que obter colisións, o que en definitiva
motiva este fío.
Que, aínda que comezar a fantasía aquí, e comezar a ter esas cadeas, aínda estamos
terá colisións.
>> Así que levanta a cuestión: o que é o custo de facer insercións e borrados
nunha estrutura de datos como este?
Ben, deixe-me propor -
e déixeme volver á pantalla sobre aquí - se temos n elementos no
lista, polo que, se estamos tentando introducir n elementos e temos
cantos total de baldes?
Digamos que 31 baldes totais no caso de aniversario.
Cal é a lonxitude máxima dun destas cadeas potencialmente?
>> Novamente non se pode 31 aniversarios en un mes.
E estamos só a aglutinación todos -
en realidade, iso é un exemplo parvo.
Imos facer 26 en vez.
Entón, se realmente ten persoas cuxos nomes comezar a Z, dando así
nos 26 posibilidades.
E nós estamos a usar unha estrutura de datos como o que acabamos de ver, en que temos
unha matriz de puntos, cada un dos cales apunta a unha lista ligada, onde a
primeira lista é de todos co nome de Alice.
A segunda lista é cada un co nome comezar coa, comezando
con B, e así por diante.
>> Cal é a duración probable de cada un dos estas listas se asumirmos unha boa limpo
distribución de nomes da a Z a través da estrutura de datos enteiro?
Hai n persoas na estrutura de datos dividido por 26, se son ben
espallados por todo o estrutura de datos.
Así, a lonxitude de cada un destes cadeas é n dividido por 26.
Pero na notación O gran, o que é iso?
¿Que é iso mesmo?
Entón, é realmente só n, non?
Porque xa dixen no pasado, Ugh que dividir por 26.
Si, en realidade é máis rápido.
Pero, en teoría, non é fundamentalmente todo o que máis rápido.
>> Polo tanto, non parece ser todo o que moito máis próximo a este Santo Graal.
En realidade, este é só o tempo lineal.
Heck, neste punto, por que non nós non necesitará empregar unha lista ligada enorme?
Por que non usar só un enorme matriz para almacenar os nomes das
todos na sala?
Ben, aínda hai algo convincente sobre unha táboa hash?
Hai aínda algo atractivo sobre unha estrutura de datos
que se parece con isto?
Este.
>> Estudante: [inaudível].
>> COLUMNA 1: Correcto, e, de novo, se non é máis un algoritmo de tempo lineal, e un
estrutura de datos en tempo lineal, por que non me só almacenar o nome de todos nun gran
matriz, ou nunha lista vinculada grande?
E deixar de facer CS moito máis difícil do que debe ser?
O que é interesante sobre iso, aínda aínda que rabuñou-lo?
>> Estudante: [inaudível].
>> COLUMNA 1: As insercións non son?
Expensive máis.
Entón insercións potencialmente podería aínda ser de tempo constante, aínda que os seus datos
estrutura parécese tanto, unha serie de enlaces, cada un dos cales está a apuntar
potencialmente unha lista encadeada.
Como podería conseguir constante inserción canto de nomes de?
Cole-o na fronte, non?
>> Sacrificarse un obxectivo do proxecto de anteriormente, onde queriamos manter
nome de todos, por exemplo, clasificadas ou todos os números en fase clasificados,
supoñer que temos un lista ligada indiferenciados.
El só nos custa un ou dous pasos, como no caso de Ben e Brian
anteriormente, para introducir un elemento en o inicio da lista.
Entón, se non nos importa sobre a clasificación todo dos nomes comezan con un ou todos
os nomes que comezan con B, aínda podemos acadar a inserción de tempo constante.
Agora, ollando para Alicia ou Bob ou calquera nome máis xeral aínda o que é?
É grande o de n dividido por 26, o caso ideal onde todo o mundo é uniforme
distribuídos onde hai o maior número dun xa que hai de Z, o cal pode ser
irrealista.
Pero iso aínda é lineal.
>> Pero aquí, volvemos ao punto de notación asintótica ser
en teoría verdade.
Pero no mundo real, se eu afirmar que meu programa pode facer algo 26 veces
máis rápido que o seu, cuxo programa vai preferir usar?
Seu ou meu, que é 26 veces máis rápido?
Realista, a persoa de quen é 26 veces máis rápido, aínda que teoricamente
nosos algoritmos son executados no mesmo asintótica tempo de carreira.
>> Deixe me propoñer unha diferente solución completamente.
E se isto non explotar a súa mente, estamos fóra de estruturas de datos.
Polo tanto, esta é unha trie -
tipo de un nome estúpido.
Provén de recuperacións, ea palabra está escrito trie, t-r-i-e, por mor de
recuperación curso soa como trie.
Pero esta é a historia da palabra trie.
>> Así, unha trie é de feito unha especie de árbore, e tamén é unha brincadeira coa palabra.
E aínda que non pode velo con esta visualización, un trie é un
árbore estructurada, como unha árbore xenealóxica con un antepasado na parte superior e moi
de netos e bisnetos como follas na parte inferior.
Pero cada nodo nun trie é unha matriz.
E é nunha matriz - e imos simplificar por un momento - é unha
matriz, neste caso, de tamaño 26, onde cada nó é de novo unha matriz de tamaño
26, onde o elemento de orde cero, no que Unha matriz representa, ea última
en cada elemento de tal array representa Z.
>> Así, propoño, entón, que estes datos estrutura, coñecida como unha trie, se pode
tamén utilizada para almacenar palabras.
Vimos hai pouco como poderiamos almacenar palabras, ou neste caso os nomes, e nós
vimos como podemos almacenar números, pero concentrarse en nomes ou secuencias
aquí, entender o que é interesante.
Eu afirmo que o nome é Maxwell dentro desta estrutura de datos.
Onde se ve Maxwell?
>> Estudante: [inaudível].
>> COLUMNA 1: Á esquerda.
Entón, o que é interesante con estes datos estrutura é, en vez de almacenar o
corda M-A-X-W-E-L-L invertida cero, todo contigua, o que facer en vez
está seguindo.
Se esta é unha estrutura de datos como trie, cada un dos nós cuxas é de novo unha matriz,
e quere almacenar Maxwell, primeiro índice e así nó da raíz, de xeito
dicir, o nodo superior, na posición M, certo, entón
aproximadamente no medio.
E, a continuación, a partir de aí, seguir unha punteiro para un neno nós, por así dicir.
Así, no sentido de árbore xenealóxica, vostede segui-lo para abaixo.
E que leva-lo a outro nodo Á esquerda, que é
só outra matriz.
>> E entón se quere gardar Maxwell, atopar o punteiro que representa
A, que é este aquí.
Entón vai ao seguinte nodo.
E teña en conta - é por iso que a imaxe do un pouco erro -
este nodo ollar super pequeno.
Pero á dereita deste é Y e Z. É só o autor ten truncado o
imaxe de xeito que realmente ver as cousas.
En caso contrario, esta imaxe sería moi grande.
Entón, agora índice para localización X, entón W, E, a continuación, L, entón L. Entón cal é
esa curiosidade?
>> Ben, se estamos a usar este tipo de nova asumir a forma de almacenar unha cadea nun
estrutura de datos, aínda que esencialmente marcar nos datos
estructura de que unha palabra remata aquí.
Noutras palabras, cada un destes nós dalgún xeito ten que lembrar que
en realidade, seguido todos estes punteiros e están deixando un pouco
migas de pan no fondo aquí deste estrutura para indicar M-A-X-W-E-L-L é
de feito nesta estrutura de datos.
>> Así, poderiamos facelo do seguinte xeito.
Cada un dos nós na imaxe que acabamos de ten unha serra, unha matriz de tamaño 27.
E agora é 27 porque, p definir seis anos, imos realmente darlle unha apóstrofe,
así podemos ter nomes como O'Reilly e outros con apóstrofos.
Pero a mesma idea.
Cada un destes elementos no puntos de matriz para unha struct
no, entón só un nó.
Entón iso é moi recorda da nosa lista encadeada.
>> E entón eu teño un valor booleano, que vou chamar palabra, que só será
certo se a palabra remata neste nodo da árbore.
El representa efectivamente poucos triángulo que vimos hai pouco.
Así, se unha palabra que remata no nó no árbore, aquel campo palabra será verdadeira,
que é conceptualmente a comprobación off, ou estamos deseñando ese triángulo, si, hai
é unha palabra aquí.
>> Polo tanto, esta é unha trie.
E agora a pregunta é, o que é o seu tempo de execución?
É grande o de n?
É algo máis?
Ben, se ten n nomes nestes datos estrutura, Maxwell sendo só un
los, o que é o tempo de execución inserción ou atopar Maxwell?
Cal é o tempo de execución inserción de Maxwell?
Se hai n outros nomes xa enriba da mesa?
Si?
>> Estudante: [inaudível].
>> COLUMNA 1: Si, é a lonxitude do nome, non?
Entón M-a-x-w-e-l-l polo que se sente así O algoritmo é grande de sete.
Agora, obviamente, o nome pode variar en lonxitude.
Quizais sexa un nome curto.
Quizais sexa un nome máis longo.
Pero o que é importante aquí é que é un número constante.
E quizais non sexa realmente constante, Pero Deus, si realista, nun
dicionario, probabelmente hai algún límite sobre o número de letras dunha
o nome da persoa nun determinado país.
>> E así, podemos supoñer que é un valor constante.
Non sei o que é.
É, probablemente, maior que pensamos que é.
Porque sempre hai algún recuncho caso cun nome moi tolo.
Entón, imos chamalo de k, senón que é un constante, presumiblemente, que cada
nome no mundo, polo menos nun determinado país, é que a lonxitude ou
máis curto, polo que é constante.
Pero cando dixemos algo é grande O dun valor constante, o que é iso
realmente equivalente a?
Esta é realmente o mesmo que dicir de tempo constante.
>> Agora somos o tipo de trapaça, non?
Estamos medio alavancar algunha teoría aquí para dicir que o ben, a fin de k é
realmente só encargar dun, e é tempo constante.
Pero realmente é.
Porque o insight clave aquí é que si temos n nomes xa neste
estrutura de datos, e inserción Maxwell é a cantidade de tempo que nos leva a
introducir Maxwell en todos os afectados por cantas outras persoas
están dentro da estrutura de datos?
Non parece ser.
Se eu tivese un bilhão de máis elementos para esta trie, e entón introduza Maxwell, é
el en todos os afectados?
Non
E iso é distinto de calquera dos datos do día estruturas que vimos ata agora, onde
o tempo de execución do algoritmo é totalmente independente de canto
material é ou non é xa en que a estrutura de datos.
>> E así, con esta proporciónalle agora é un oportunidade para p conxunto de seis, que será
novo involucrar aplicar o seu propio corrector ortográfico, a lectura en 150 mil
palabras, o mellor xeito de gardar este non é necesariamente evidente.
E aínda que eu aspiraba a atopar o Santo Graal, eu non
afirman que unha trie é.
De feito, unha táboa hash pode moi ben probar ser moito máis eficiente.
Pero estes son só -
iso é só unha das decisións de proxecto terá que facer.
>> Pero no peche teremos 50 ou máis segundos para dar un ollo ao que está
fronte a próxima semana e que a transición ademais dende esta liña de comandos
mundo, programas en C para as cousas web base e linguaxes como PHP e
Javascript e da propia Internet, protocolos como HTTP, o que
tida como certa por moitos anos agora, e escribiu a maioría cada
día, quizais, ou ver.
E imos comezar a pelar a capas de cal é a Internet.
E cal é o código que subxacente ferramentas de hoxe.
Entón 50 segundos este teaser aquí.
Eu darlle guerreiros da rede.
>> [REPRODUCIÓN]
>> -El veu cunha mensaxe.
Cun protocolo de todos os seus propios.
Chegou a un mundo de firewalls crueis, routers indiferente, e os perigos lonxe
peor que a morte.
El é rápido.
El é forte.
El é TCPIP.
E el ten o seu enderezo.
Guerreiros da rede.
>> [FIN reprodución de vídeo]
>> COLUMNA 1: É así que a Internet debe traballar desde a próxima semana.