[Powered by Google Translate] [Tutorial - Set Problema 5]
[Zamyla Chan - Harvard University]
[Esta es CS50. - CS50.TV]
>> Está bien. Hola a todos y bienvenidos a Tutorial 5.
>> Pset5 es Errores de ortografía, en el que vamos a hacer un corrector ortográfico.
Correctores ortográficos son extremadamente importantes.
Le ha sucedido esto a usted?
Se trabaja muy, muy acumular en un papel para un choque
y aún así terminar encima de conseguir un brillo muy rade como una D o una = D
y todo porque usted es el paté de hígado alerón en la palabra ballena de ancho.
Sí, revisión tus pimientos es una cuestión de la máxima impotencia.
Este es un problema que afecta a los estudiantes masculinos, viriles.
Una vez me dijeron a mi torturador grado sith que nunca me metería en un buen colega.
Y eso es todo lo que quería, eso es todo lo que cualquier chico quiere a mi edad,
sólo para llegar a un buen colega.
Y no cualquier colega. No. Yo quería ir a un colega de Marfil Legal.
Así que si no me mejora, se ha ido serían mis sueños de ir a Harvard,
Jale, o Prisión - usted sabe, en la prisión, Nueva Jersey.
Así que me compré un corrector ortográfico.
Eso es un fragmento pequeño de una de mis artistas favoritas palabra hablada, Taylor Mali.
De todos modos, como él dice, la importancia de contar con un corrector ortográfico es muy importante.
>> Así que bienvenido a Tutorial 5, en el que vamos a estar hablando de pset5: Errores de ortografía,
en el que vamos a hacer nuestro propio corrector ortográfico.
La caja de herramientas para esta semana, el código de distribución, va a ser importante tener en cuenta
sólo para entender las diferentes funciones que el diccionario se va a tener.
Estamos realmente va a tener archivos múltiples c. Que conforman nuestro conjunto de procesadores.
Y así, mirando a través de los diferentes aspectos, a pesar de que no estamos en realidad edición
uno de los archivos, speller.c, sabiendo cómo funciona con relación a dictionary.c,
que vamos a estar escribiendo, va a ser muy importante.
La especificación pset también contiene una gran cantidad de información útil
en términos de cosas que usted puede asumir, reglas y cosas por el estilo,
así que asegúrese de leer la especificación del conjunto de procesadores con cuidado por las propinas.
Y ante la duda de una regla o algo así, entonces siempre se refieren a la especificación de conjunto de procesadores
o discutir.
Este conjunto de procesadores va a depender en gran medida de los punteros,
por lo que queremos asegurarnos de que entendemos la diferencia entre las estrellas añaden
delante del nombre del puntero y símbolos de unión, la manera de liberarlos, etc
Así que ser un maestro de punteros va a ser muy útil en este conjunto de problemas.
Vamos a mirar en las listas enlazadas un poco más,
donde tenemos elementos que nos llaman nodos que tienen tanto un valor, así como un puntero
al nodo siguiente, y así esencialmente que une los diferentes elementos uno tras otro.
Hay algunas opciones diferentes de implementar el diccionario actual.
Vamos a examinar dos métodos principales, que es tablas hash y luego trata.
En ambos de aquellos, implican algún tipo de concepto de una lista enlazada
donde se han elementos vinculados entre sí.
Así que vamos a revisar cómo usted puede ser capaz de operar en torno a las listas enlazadas,
crear ellos, navegar en términos de la forma de, por ejemplo, insertar un nodo en ella
o libre de todos los nodos.
En cuanto a los nodos de desagüe, eso es muy importante
que cada vez que la memoria malloc, después que lo libere.
Así que queremos asegurarnos de que no va unfreed puntero, que no tenemos las fugas de memoria.
Vamos a introducir una herramienta llamada Valgrind que se ejecuta el programa
y comprueba si toda la memoria asignada es entonces liberado.
Su conjunto de procesadores sólo está completa cuando trabaja y cuando su funcionalidad sea completa,
sino también, Valgrind te dice que no hemos encontrado ninguna pérdidas de memoria.
Por último, para este conjunto de procesadores, lo que realmente quiero hacer hincapié en -
Quiero decir, como de costumbre, yo soy definitivamente partidario de usar la pluma y el papel para los conjuntos de problemas,
pero para esto, creo que la pluma y el papel que va a ser especialmente importante
cuando se quiere estar dibujando flechas a las cosas y entender cómo funcionan las cosas.
Así que sin duda intenta utilizar lápiz y papel para dibujar las cosas antes de que te codificación
porque podría ser un poco desordenado.
>> En primer lugar, vamos a entrar en las listas enlazadas un poco.
Las listas enlazadas consisten de nodos, donde cada nodo tiene un valor asociado con ella,
así como un puntero al siguiente nodo después de ella.
Un par de cosas importantes con las listas enlazadas es que tenemos que recordar
donde nuestro primer nodo es, y luego una vez que sabemos que es el primer nodo,
de esa manera podemos acceder al nodo que los puntos de primer nodo
y luego el uno después de eso y el después de eso.
Y el último elemento de la lista enlazada es puntero ese nodo
siempre va a apuntar a NULL.
Cuando un puntos de nodo a NULL, entonces usted sabe que usted ha llegado al final de la lista,
que ese nodo es el último, que no hay nada después de eso.
Aquí, en este esquema, se ve que las flechas son los punteros,
y la sección azul es donde se almacena el valor,
y luego el cuadro rojo con el puntero es puntero del nodo
apuntando al siguiente nodo después de ella.
Y por lo que veo aquí, el nodo D apuntaría a NULL, ya que es el último elemento de la lista.
>> Vamos a ver cómo podemos definir una estructura para un nodo.
Y ya que queremos tener varios nodos,
esto va a ser un typedef struct
en el que vamos a tener varias instancias diferentes de nodos.
Y así lo definen como un nuevo tipo de datos.
Aquí tenemos un nodo typedef struct.
En este ejemplo, estamos tratando con nodos enteros,
por lo que tenemos un valor entero llamado y luego tenemos otro puntero,
y en este caso, es un puntero a un nodo, por lo que tiene un nodo de estructura * llamada siguiente.
Y entonces estamos llamando a este nodo todo.
Asegúrese de que usted siga esta sintaxis.
Observe que el nodo se hace referencia en realidad por encima como por debajo de las llaves.
A continuación, hacer un seguimiento de dónde está mi primer nodo está en esta lista enlazada,
entonces tiene un puntero nodo llamado cabeza, y el espacio malloc suficiente para el tamaño de un nodo.
Nótese, sin embargo, que la cabeza es en realidad un puntero nodo en lugar de un nodo en sí.
Así la cabeza en realidad no contiene ningún valor,
sólo apunta a lo que el primer nodo en mi lista enlazada es.
>> Para tener una mejor idea de las listas enlazadas, porque es muy importante
para realizar un seguimiento de asegurar el mantenimiento de la cadena,
Me gusta pensar en ello como la gente en una línea de la mano,
donde cada persona está de la mano con la siguiente.
No se puede ver en este dibujo, pero en el fondo están apuntando a la siguiente persona
que es en su cadena.
Así que si usted desea recorrer una lista enlazada donde estas personas -
imaginar todas esas personas tienen valores asociados a ellas
y también apuntar a la siguiente persona en la línea -
si usted desea recorrer la lista vinculada, por ejemplo, para editar los valores por
o buscar un valor o algo así,
entonces usted querrá tener un puntero a la persona en concreto.
Así que vamos a tener un tipo de datos de puntero de nodo.
Para este ejemplo, vamos a llamarlo cursor.
Otra forma común de nombrar esto sería iterador o algo por el estilo
porque es iterar sobre y en realidad mueve el nodo que se está señalando.
Esto aquí será nuestro cursor.
Nuestro primer cursor apuntará al primer elemento de la lista.
Así que lo que quiero hacer es que básicamente se sigue el cursor,
moviéndolo de lado a lado.
En este caso, queremos pasar a la siguiente elemento de la lista.
Con los arreglos, lo que nosotros hacemos es simplemente diría que aumentar el índice 1.
En este caso, lo que tenemos que hacer es encontrar realmente que esta persona persona corriente que hace referencia,
y que va a ser el siguiente valor.
Así que si el cursor es un puntero de nodo, entonces lo que quiero hacer
es que queremos llegar al valor que el cursor está apuntando.
Queremos llegar a ese nodo y, a continuación, una vez que estamos en ese nodo, encontrar dónde está apuntando.
Para llegar al nodo actual que el cursor está apuntando,
por lo general nos indican por (cursor *).
Eso le daría el nodo actual que el cursor está apuntando.
Y después de eso, lo que queremos hacer es que queremos acceder
lo que el siguiente valor de nodo es.
Para ello, para acceder a los valores dentro de la estructura, tenemos el operador punto.
Entonces sería (cursor *). Siguiente.
Pero esto es un poco complicado en términos de tener los corchetes alrededor del cursor *,
por lo que reemplazar esta declaración con toda cursor->.
Este es un guión y luego una señal mayor que, por lo que hacer una flecha.
cursor-> siguiente.
Que en realidad le conseguirá el nodo que el cursor apunte a. Ese valor es de siguiente.
Así que en lugar de tener la estrella y el punto, usted está reemplazando que con una flecha.
Tenga mucho cuidado para asegurarse de que intenta utilizar esta sintaxis.
>> Ahora que tenemos nuestro cursor, si queremos acceder al valor,
antes, teníamos cursor-> siguiente,
pero para acceder al valor en el nodo que el cursor hace referencia, que simplemente decir
nodo-> valor.
A partir de ahí, es del tipo de datos lo que hemos definido los valores y los nodos a ser.
Si se trata de un nodo int, entonces cursor-> valor es sólo va a ser un número entero.
Así que podemos hacer operaciones en eso, comprobar igualdades, asignarle valores diferentes, etc
Así que lo que quiere hacer si desea mover el cursor a la siguiente persona,
realmente cambiar el valor del cursor.
Desde cursor es un puntero nodo, se cambia la dirección del puntero actual
a la dirección del nodo siguiente en su lista.
Esto es sólo parte del código donde se puede iterar.
Donde tengo el comentario de hacer algo,
ahí es donde usted está probablemente va a tener acceso al valor
o hacer algo que ver con ese nodo específico.
Para empezar, tengo que decir que mi cursor al principio
se va a apuntar al primer elemento en la lista enlazada.
Y más adelante, lo define como la cabeza del nodo.
>> Como mencioné antes, la liberación es muy importante.
Usted quiere asegurarse de que liberar a todos los elementos de la lista una vez que haya terminado con él.
Cuando no es necesario hacer referencia a cualquiera de los punteros más,
usted quiere asegurarse de que liberar a todos los punteros.
Pero quiero ser muy cuidadosos en este punto en que se quiere evitar cualquier fuga de memoria.
Si una persona antes de tiempo libre, entonces todos los punteros que para que los puntos de unión
van a perder.
Volviendo al ejemplo de persona para que sea un poco más altas estacas,
vamos a tener a esta gente, sólo que en este caso se cierne sobre un lago con un monstruo.
Queremos asegurarnos de que cada vez que liberarse, no perdemos
y dejar de lado los nodos antes de que hayamos hecho los liberó.
Por ejemplo, si usted fuera a llamar simplemente gratuitamente en este tipo aquí,
entonces sería liberado, pero luego todos estos chicos luego se perdería
y ellos quedarse dormido y caerse.
Así que queremos asegurarnos de que por el contrario, queremos mantener un vínculo con el resto.
Nuestra cabeza puntero, que apunta al primer elemento de la lista.
Es algo así como una cuerda de anclaje en la primera persona.
Lo que usted puede ser que desee hacer cuando se libera un lista se tiene -
Si desea liberar el primer elemento en primer lugar, entonces usted puede tener un puntero temporal
que apunta a lo que el primer elemento es.
Así que tienes el puntero temporal señalando aquí.
De esta manera, tenemos un asimiento del primer nodo.
Y entonces, ya sabemos que el primer nodo va a ser liberado,
entonces podemos mover la cuerda, esta ancla, nuestra cabeza,
señalar realmente a cualquiera que sea el primero está apuntando.
Así que esta cabeza en realidad apunta al segundo elemento ahora.
Ahora se nos permite liberar todo lo que se almacena en temp,
y para que podamos borrar sin que ello ponga en peligro a todos los demás nodos de la lista.
Otra forma en que usted puede hacer esto podría ser
cada vez que se acaba de liberar el último elemento de la lista
porque se garantiza que no se refirió a ninguna parte.
Por lo que sólo podría liberar este, entonces sin éste, entonces libre de éste.
Eso definitivamente funciona, pero es un poco más lento porque por la naturaleza de las listas enlazadas,
no podemos saltar inmediatamente a la última.
Tenemos que atraviesan cada elemento de la lista enlazada
y comprobar si aquél está apuntando a NULL, comprobar cada vez,
y luego una vez que llegamos a la final, entonces sin eso.
Si se va a realizar este proceso, que en realidad sería el registro aquí,
comprobar aquí, a continuación, comprobar aquí, liberándola,
luego volver, comprobando aquí, revisando aquí, liberándola,
comprobando aquí, y luego liberar.
Para eso se necesita algo más de tiempo. Si.
>> [Estudiante] ¿Sería posible hacer una lista enlazada que almacena un puntero de salida hasta el final?
Que sin duda sería posible.
Para repetir la pregunta, es posible tener una estructura de lista enlazada
de tal manera que tiene un puntero que señala el final de la lista enlazada?
Yo diría que eso es posible, y cada vez que se inserta algo en tu lista enlazada
usted tendría que actualizar ese puntero y cosas por el estilo.
Usted tendría una cola * nodo, por ejemplo.
Pero cuando estás implementar esta característica, usted tiene que pensar en las ventajas y desventajas,
como cuántas veces voy a estar interactuando sobre esto,
lo difícil es que va a ser para realizar un seguimiento de la cola y la cabeza del
así como mi iterador, y cosas por el estilo.
¿Eso - >> [Estudiante] Yeah.
Es posible, pero en términos de decisiones de diseño, usted tiene que sopesar las opciones.
>> Aquí hay un esqueleto de código que le permitirá liberar a todos los elementos de una lista enlazada.
Una vez más, ya que estoy iterar sobre una lista enlazada, voy a querer tener algún tipo de cursor
o iterador.
Estamos iterando hasta que el cursor es NULL.
No quiero repetir cuando el cursor es NULL
porque eso significa que no hay nada en la lista.
Así que aquí hago un nodo temporal *
apuntando a lo que estoy considerando es el primero de mi lista,
y luego muevo mi cursor delante 1 y luego libre todo lo que yo tenía en el almacenamiento temporal.
>> Ahora llegamos a la inserción en listas enlazadas.
Tengo tres nodos en mi lista enlazada, y vamos a ir con el caso simple
donde queremos insertar un nodo al final de nuestra lista enlazada.
Para ello, lo único que haría es que atravesaría
para encontrar dónde está el final actual de la lista enlazada es, por lo que cualquier nodo apunta a NULL -
que es éste -
y luego decir, en realidad, éste no va a ser el último nodo;
hecho vamos a tener otro.
Así que tendría esta corriente un punto a lo que estamos insertando.
Así que ahora esta persona rojo se convierte aquí en el último nodo en la lista enlazada.
Y así, la característica del último nodo de la lista enlazada es que apunta a NULL.
Así que lo que tendríamos que hacer es establecer el puntero de este tipo de rojo a NULL. Ya está.
>> Pero lo que si queremos insertar un nodo entre la segunda y la tercera?
Que uno no es tan sencillo, porque queremos asegurarnos
que no dejamos de lado cualquier nodo de la lista ligada.
Lo que tendría que hacer es asegurarse de que nos ancla a cada uno.
Por ejemplo, vamos a llamar a este el segundo.
Si usted dijo que el segundo apunta ahora a esta nueva
y que acaba de hacer un puntero ahí, pues, que daría lugar a un tipo que se pierdan
porque no hay ningún vínculo con él.
En su lugar - Voy a llamar de nuevo. Perdona mis habilidades artísticas.
Sabemos que no podemos conectar directamente 2 a la nueva.
Tenemos que asegurarnos de que nos aferramos a la última.
Lo que puede ser que desee hacer es tener un puntero temporal
para el elemento que va a ser añadido en.
Así que tenemos un puntero temporal allí.
Como sabemos que esta tercera se mantiene un seguimiento de,
2 ahora se puede vincular a nuestro uno nuevo.
Y si este nuevo tipo rojo va a ser entre 2 y 3,
entonces lo que se puntero de ese tipo va a señalar? >> [Estudiante] Temp.
Temperatura Si.
Así que el siguiente valor a este tipo de rojo va a ser temporal.
Cuando usted está insertando en las listas enlazadas, vimos que podíamos
fácilmente añadir algo al final mediante la creación de una matriz temporal,
o si quería añadir algo en el medio de nuestra matriz,
entonces se necesitaría un poco más arrastrando los pies alrededor.
Si lo desea, por ejemplo, tienen una lista ordenada vinculado,
entonces usted tiene que tipo de sopesar los costos y beneficios de esa
porque si usted quiere tener un arreglo ordenado, lo que significa que cada vez que se inserta en ella,
que va a tomar un poco más tiempo.
Sin embargo, si desea más adelante, ya que encontraremos vamos a querer,
búsqueda a través de una lista enlazada, entonces podría ser más fácil si usted sabe que todo está en orden.
Así que es posible que desee considerar los costos y beneficios de eso.
>> Otra manera de insertar en una lista enlazada es para insertar en el principio de una lista.
Si dibujamos el ancla aquí - esta es nuestra cabeza -
y luego tener estas personas vinculadas a la misma,
y entonces tenemos un nuevo nodo a ser insertado en el inicio,
entonces lo que queremos hacer?
¿Qué tendría de malo diciendo que desea vincular el rojo al azul,
porque esa es la primera?
¿Qué pasaría aquí?
Todos estos tres se pierden.
Así que no quiero hacer eso.
Una vez más, hemos aprendido que tenemos que tener algún tipo de puntero temporal.
Vamos a optar por tener un punto temporal a este tipo.
Entonces podemos tener la nada un punto al temporal
y luego el punto rojo al azul.
La razón por la que estoy usando a la gente aquí es porque realmente quiere visualizar
aferrándose a la gente y asegurarse de que tenemos un link a las mismas
antes de soltar otra mano o algo así.
>> Ahora que tenemos una idea de las listas enlazadas - cómo podríamos crear una lista enlazada
y crear las estructuras para que consta de la definición de tipo de un nodo
y luego asegurarse de que tenemos un puntero a la cabeza de esa lista enlazada -
una vez que tengamos eso y sabemos cómo recorrer a través de una matriz,
acceder a los diferentes elementos, sabemos cómo insertar y sabemos cómo liberarlos,
entonces podemos entrar en faltas de ortografía.
Como es habitual, tenemos una sección de preguntas que se utilizó para operar con listas enlazadas
y diferentes estructuras como colas y pilas.
Entonces podemos pasar a errores ortográficos.
>> Errores de ortografía tiene en el código de distribución de un par de archivos de importancia.
En primer lugar nos damos cuenta de que tenemos este Makefile aquí,
que en realidad no hemos visto antes.
Si se miraba en el interior de la carpeta pset5, te darías cuenta de que tiene un archivo. H,
entonces tienes dos archivos. c.
Lo que esto hace es Makefile antes, sólo tendría que escribir y hacer luego el nombre del programa
y entonces veríamos todos estos argumentos y banderas pasado en el compilador.
Lo que el Makefile que hace es que nos permite compilar varios archivos a la vez
y pasar las banderas que queremos.
Aquí sólo ver que hay un archivo de cabecera aquí.
Entonces en realidad tenemos dos archivos de código fuente.
Tenemos speller.c y dictionary.c.
Le invitamos a editar el Makefile si lo desea.
Tenga en cuenta que aquí si escribe limpia, entonces lo que hace es en realidad elimina cualquier cosa
que es el núcleo.
Si tienes un error de segmentación, básicamente se obtiene un volcado de memoria.
Así que este pequeño archivo feo aparecerá en el directorio llamado núcleo.
Usted querrá quitar eso para hacer la limpieza.
Elimina todos los archivos exe y. Archivos o.
>> Vamos a echar un vistazo a dictionary.h.
Esto dice que se declara la funcionalidad de un diccionario.
Contamos con una longitud máxima de cualquier palabra en el diccionario.
Decimos que esto va a ser la palabra más larga posible. Es de longitud 45.
Así que no vamos a tener ninguna palabra que exceden esa longitud.
Aquí sólo tenemos los prototipos de funciones.
No tenemos la aplicación real porque eso es lo que vamos a hacer en este conjunto de procesadores.
Pero lo que hace esto es debido a que estamos tratando con archivos más grandes aquí
y funcionalidad en una escala más grande, es útil disponer de un archivo. h
para que otra persona la lectura o el uso de su código puede entender lo que está pasando.
Y tal vez desee implementar intenta si lo hizo tablas hash o viceversa.
Entonces diría que mi función de carga,
la aplicación real que se va a diferir, pero este prototipo no va a cambiar.
Aquí hemos comprobar, que devuelve verdadero si una palabra dada está en el diccionario.
Entonces tenemos carga, que, básicamente, tiene en un archivo de diccionario
y luego se carga en alguna estructura de datos.
Tenemos tamaño, que, cuando es llamada, devuelve el tamaño de su diccionario,
cuántas palabras se almacenan en el mismo,
y descarga, lo que libera toda la memoria que usted puede haber tomado
al tiempo que su diccionario.
>> Vamos a echar un vistazo a dictionary.c.
Vemos que es muy similar a dictionary.h, excepto que ahora sólo tiene todas estas TODOs en ella.
Así que es tu trabajo. Con el tiempo, se le rellenando speller.c con todo este código.
Dictionary.c, cuando se ejecuta, no es realmente va a hacer nada,
así que mirar hacia speller.c para ver la aplicación real de la corrección ortográfica.
A pesar de que usted no va a ser la edición de cualquiera de este código,
es importante leer, comprender cuando se carga llamara, cuando estoy llamando cheque,
sólo para entender, asigne a cabo, ver cómo trabaja la función.
Vemos que se está comprobando el uso correcto.
Esencialmente, cuando alguien se queda speller, esto indica que es opcional
para que puedan pasar en un archivo de diccionario, porque no va a ser un archivo de diccionario por defecto.
Y luego tienen que pasar en el texto que se va revise la ortografía.
ofertas rusage con el tiempo porque una parte de este conjunto de procesadores que nos ocuparemos más adelante
no sólo para conseguir un funcionamiento corrector ortográfico de trabajo
pero en realidad cada vez que sea rápido.
Y entonces ahí es donde rusage va a venir pulg
Aquí, vemos la primera llamada a uno de nuestros archivos dictionary.c, que es de carga.
Carga devuelve verdadero o falso - verdadero en el éxito, false en caso de fallo.
Así que si el diccionario no se carga correctamente, entonces el speller.c devolverá 1 y dejar de fumar.
Pero si se carga correctamente, entonces va a continuar.
Seguimos, y vemos algún archivo I / O aquí,
donde va a estar tratando con abrir el archivo de texto.
Aquí, lo que hace es corrector comprueba cada palabra en el texto.
Entonces, ¿qué está haciendo speller.c aquí se itera sobre cada una de las palabras en el archivo de texto
y luego la comprobación en el diccionario.
Aquí tenemos un booleano mal escrita que ver si el cheque devuelve true o no.
Si la palabra es en realidad en el diccionario, entonces cheque devolverá true.
Eso significa que la palabra no está mal escrito.
Así que mal escrito sería falso, y es por eso que tenemos la explosión allí, la indicación.
Seguimos adelante, y luego se hace un seguimiento de la cantidad de palabras mal escritas
existen en el archivo.
Se sigue y cierra el archivo.
Entonces aquí, se informa de la cantidad de palabras mal escritas que tenía.
Calcula la cantidad de tiempo que se tardó en cargar el diccionario,
cuánto tiempo se tardó en comprobar,
la cantidad de tiempo que tomó para calcular el tamaño,
que, como veremos adelante, debe ser muy pequeña,
y ¿cuánto tiempo se tardó en descargar el diccionario.
Aquí arriba podemos ver la llamada a descargar aquí.
Si vamos a comprobar el tamaño aquí,
entonces podemos ver que aquí es la llamada a tamaño, donde determina el tamaño del diccionario.
Awesome.
>> Nuestra tarea en este conjunto de procesadores es la implementación de carga, que se carga el diccionario
estructura de datos - lo que usted elija, ya sea una tabla hash o intentar a -
con palabras del archivo de diccionario.
Entonces usted tiene tamaño, que devolverá el número de palabras en el diccionario.
Y si implementa la carga de una manera inteligente, a continuación, el tamaño debe ser bastante fácil.
Entonces usted ha cheque, que comprobará si una palabra dada está en el diccionario.
Así speller.c pasa en una cadena, y entonces usted tiene que comprobar si esa cadena
está contenida dentro de su diccionario.
Tenga en cuenta que por lo general tenemos los diccionarios estándar,
pero en este conjunto de procesadores, básicamente cualquier diccionario aprobada en en cualquier idioma.
Así que no podemos asumir que la palabra la que hay dentro.
El FOOBAR palabra puede ser definido en un diccionario seguro que pasamos pulg
Y entonces hemos descarga, lo que libera el diccionario de la memoria.
>> En primer lugar, me gustaría ir sobre el método de la tabla de hash
acerca de cómo podemos poner en práctica todas esas cuatro funciones,
y luego voy a ir sobre la trata de método, cómo aplicar esas cuatro funciones,
y al final de la conversación sobre algunos consejos generales cuando estás haciendo el conjunto de procesadores
y también cómo es posible que pueda usar Valgrind para comprobar si hay fugas de memoria.
>> Vamos a entrar en el método de la tabla hash.
Una tabla hash consiste en una lista de cubos.
Todos los valores, cada palabra, se va a ir a uno de estos cubos.
Una tabla hash idealmente distribuye de manera uniforme todos esos valores que está pasando en
y luego se rellena en el cubo de tal manera que cada cubo
tiene aproximadamente el mismo número de valores en ella.
La estructura de una tabla hash, tenemos una serie de listas enlazadas.
Lo que hacemos es cuando se pasa de un valor, donde se comprueba que el valor debería pertenecer,
que cubo al que pertenece, y luego se coloca en la lista enlazada asociada a ese cubo.
Aquí, lo que tengo es una función hash.
Es una tabla hash int.
Así que para el primer segmento, cualquier número entero por debajo de 10 entran en el primer cubo.
Los números enteros superiores a 10 pero inferior a 20 ir a la segunda,
y, a continuación así sucesivamente y así sucesivamente.
Para mí, cada segmento representa a estos números.
Sin embargo, decir que me iban a pasar en el 50, por ejemplo.
Parece como si las tres primeras contienen una serie de diez números.
Pero yo quiero que mi tabla hash para tomar en cualquier tipo de números enteros,
entonces yo tendría que filtrar todos los números por encima de 30 en el último segmento.
Y así, pues, que se traduciría en una especie de tabla hash desequilibrada.
Para reiterar, una tabla hash es sólo un conjunto de cubos
donde cada cubo es una lista enlazada.
Y así, para determinar dónde va cada valor, el cual entra en balde,
usted va a querer lo que se llama una función hash
que toma un valor y luego dice: este valor corresponde a un cubo determinado.
Así que allá arriba, en este ejemplo, mi función hash tomó cada valor.
Se comprobó si era menos de 10.
Si lo fuera, habría que poner en el primer cubo.
Comprueba si es menor de 20, lo coloca en el segundo si es cierto,
comprueba si es menos de 30, y luego lo pone en el tercer cubo,
y entonces todo lo demás cae justo al cubo cuarto.
Así que cada vez que tenga un valor, la función hash
colocará ese valor en el cubo adecuado.
La función hash, básicamente, tiene que saber cómo cubos que tiene.
Su tamaño de la tabla hash, el número de depósitos que tiene,
que va a ser un número fijo que depende de usted, para que usted decida,
pero va a ser un número fijo.
Así que su función hash se confía en que para determinar qué cubeta cada llave entra en
tal que es uniformemente distribuida.
Al igual que en nuestra implementación de las listas enlazadas, ahora cada nodo en la tabla hash
es en realidad va a tener un tipo char.
Así que tenemos una matriz de caracteres llamado palabra y luego otro puntero al nodo siguiente,
lo cual tiene sentido porque va a ser una lista enlazada.
¿Recuerdas cuando había listas enlazadas, hice un llamado nodo * cabeza
que estaba apuntando al primer nodo en la lista enlazada.
Pero para nuestra tabla hash, ya que tenemos varias listas enlazadas,
lo que queremos es que queremos que nuestra tabla hash para ser como, "¿Qué es un cubo?"
Un cubo es simplemente una lista de punteros a nodos,
y por lo que cada elemento en el cubo está apuntando a su lista vinculado correspondiente.
Para volver a este esquema, se ve que los propios cubos son las flechas,
No nodos reales.
Una característica esencial de las funciones de hash es que son deterministas.
Eso significa que cada vez que el hash del número 2,
siempre debe devolver el mismo cubo.
Cada valor único que se dedica a la función hash, si se repite,
tiene que conseguir el mismo índice.
Así que su función hash devuelve el índice de la matriz
cuando dicho valor pertenece.
Como mencioné antes, el número de depósitos es fijo,
por lo que su índice que vuelva tiene que ser menor que el número de cubos
pero mayor que 0.
La razón por la que tenemos funciones de hash en lugar de sólo una lista simplemente enlazada
o una sola matriz es que queremos ser capaces de saltar a una determinada sección más fácilmente
si se conoce la característica de un valor -
en lugar de tener que buscar a través de todo el diccionario entero,
ser capaz de saltar a una determinada sección de la misma.
Su función hash debe tener en cuenta que, idealmente,
cada cubo tiene aproximadamente el mismo número de teclas.
Puesto que la tabla hash es una serie de listas enlazadas,
a continuación, las listas enlazadas mismos van a tener más de un nodo.
En el ejemplo anterior, dos números diferentes, a pesar de que no eran iguales,
cuando hash, volvería el mismo índice.
Así que cuando se trata de palabras, una palabra cuando hashed
sería el mismo valor hash como una palabra más.
Eso es lo que llamamos una colisión, cuando tenemos un nodo que, cuando se aplica un algoritmo hash,
la lista vinculada a ese cubo no está vacío.
La técnica que se llama sondeo lineal,
donde vaya a la lista enlazada y luego encontrar la que desea insertar el nodo
porque hay una colisión.
Se puede ver que podría haber un trade-off, ¿verdad?
Si usted tiene una tabla hash muy pequeño, un número muy pequeño de cubos,
entonces usted va a tener un montón de colisiones.
Pero entonces, si usted hace una tabla hash muy grande,
usted está probablemente va a minimizar las colisiones,
pero va a ser una estructura de datos muy grandes.
Va a ser ventajas y desventajas con eso.
Así que cuando usted está haciendo su conjunto de procesadores, trate de jugar
entre tal vez hacer una tabla hash de menor
pero a sabiendas de que va a tomar un poco más de tiempo para recorrer los diferentes elementos
de las listas enlazadas.
>> ¿Qué carga se va a hacer es iterar sobre cada palabra en el diccionario.
Se pasa un puntero al archivo de diccionario.
Así que vamos a aprovechar el archivo de funciones I / O que dominan en pset4
e iterar sobre cada palabra en el diccionario.
Usted quisiera que cada palabra en el diccionario para convertirse en un nuevo nodo,
y usted va a colocar cada uno de los nodos dentro de la estructura de datos del diccionario.
Siempre que reciba una nueva palabra, usted sabe que va a convertirse en un nodo.
Así que usted puede ir inmediatamente y malloc un puntero de nodo para cada nueva palabra que usted tiene.
Aquí estoy llamando a mi new_node puntero de nodo y estoy mallocing qué? El tamaño de un nodo.
Luego de leer la cadena real de un archivo, ya que el diccionario se almacena
por una palabra y una nueva línea, lo que podemos aprovechar
es la función fscanf,
por lo que es el archivo de diccionario que nos pasa adentro,
por lo que analiza el archivo para una cadena y coloca esa cadena en el argumento anterior.
Si se llama a una de las conferencias, cuando nos fuimos
y el tipo de pelado de las capas de nuevo en la biblioteca CS50,
vimos una implementación de fscanf allí.
Para volver a fscanf, tenemos el archivo que estamos leyendo,
estamos buscando una cadena en el archivo, y luego lo vamos a poner en
aquí tengo new_node-> new_node palabra porque es un puntero de nodo,
no un nodo real.
Así que lo que estoy diciendo new_node, quiero ir al nodo que está apuntando a
y después asignar ese valor a la palabra.
Queremos aprovechar entonces la palabra y la inserta en la tabla hash.
Darse cuenta de que hemos hecho new_node un puntero nodo
porque vamos a querer saber cuál es la dirección de nodo que es
cuando se inserta en porque la estructura de los propios nodos, de la estructura,
es que tienen un puntero a un nuevo nodo.
Entonces, ¿cuál es la dirección del nodo que va a señalar?
Esa dirección va a ser new_node.
¿Tiene sentido, ¿por qué estamos haciendo new_node a * nodo en lugar de un nodo?
Bien.
Tenemos una palabra. Ese valor es new_node-> palabra.
Que contiene la palabra del diccionario que desea ingresar.
Así que lo que quiero hacer es que queremos llamar a nuestra función hash en esa cadena
porque nuestra función hash toma una cadena y luego nos devuelve un entero,
donde ese entero es el índice de tabla hash donde en ese índice representa el cubo.
Queremos aprovechar ese índice y luego ir a ese índice de la tabla hash
y luego usar esa lista vinculada a insertar el nodo en new_node.
Recuerde que sin embargo decide insertar el nodo,
ya sea en el medio si desea ordenar
o al principio o al final, sólo asegúrese de que el último nodo siempre apunta a NULL
porque esa es la única manera de saber dónde está el último elemento de la lista enlazada es.
>> Si el tamaño es un número entero que representa el número de palabras en un diccionario,
entonces una forma de hacer esto es que cada vez que se llama tamaño
vamos a través de cada elemento en nuestra tabla hash
y luego iterar a través de cada lista enlazada dentro de la tabla hash
y luego calcular la longitud de ello, el aumento de nuestra contador 1 en 1.
Pero cada vez que el tamaño se llama, que va a tomar mucho tiempo
porque vamos a ser linealmente sondeo cada lista simplemente enlazada.
En su lugar, va a ser mucho más fácil si usted mantiene un registro de cuántas palabras se pasa pulg
Así que si usted incluye un contador dentro de su función de carga
que se actualiza según sea necesario, a continuación, contador, si lo establece en una variable global,
será capaz de acceder por tamaño.
Entonces, ¿qué tamaño podría simplemente hacer es en una sola línea, simplemente devuelva el valor del contador,
el tamaño del diccionario, que ya se trataron en carga.
Eso es lo que quise decir cuando dije que si implementa la carga de una manera útil,
entonces el tamaño va a ser bastante fácil.
>> Así que ahora tenemos que comprobar.
Ahora nos enfrentamos con las palabras del archivo de texto de entrada,
y así vamos a estar revisando si todas esas palabras de entrada
son en realidad en el diccionario o no.
Al igual que Scramble, queremos permitir que no se distingan.
Usted quiere asegurarse de que todas las palabras salieron de adentro, aunque son mayúsculas y minúsculas,
cuando se llama con cadena de comparación, son equivalentes.
Las palabras en los archivos de diccionario de texto son realmente minúsculas.
Otra cosa es que se puede asumir que cada palabra pasada en, cada cadena,
va a ser alfabético o contener apóstrofos.
Apostrophes van a ser válidos palabras en el diccionario.
Así que si usted tiene una palabra con apóstrofo S, que es una palabra real legítimo en su diccionario
que va a ser uno de los nodos de la tabla hash.
Compruebe si funciona con la palabra existe, entonces tiene que estar en nuestra tabla hash.
Si la palabra está en el diccionario, entonces todas las palabras en el diccionario se encuentran en la tabla hash,
así que vamos a buscar esta palabra en la tabla hash.
Sabemos que desde que implementamos nuestra función hash
de tal manera que cada palabra única es siempre ordenadas por el mismo valor,
entonces sabemos que en lugar de buscar a través de toda nuestra tabla hash entero,
en realidad podemos encontrar la lista enlazada que esa palabra debería pertenecer.
Si fuera en el diccionario, entonces sería en ese cubo.
¿Qué podemos hacer, si la palabra es el nombre de nuestra cadena pasada,
podemos simplemente hash que palabra y mirada a la lista enlazada
en el valor de la tabla hash [hash (palabra)].
A partir de ahí, lo que podemos hacer es que tenemos un pequeño subconjunto de nodos para buscar esta palabra,
por lo que puede atravesar la lista enlazada, con un ejemplo de antes en el tutorial,
y luego llamar a comparación de cadenas en la palabra siempre que el cursor está apuntando,
esa palabra, y ver si los que comparar.
Dependiendo de la forma en que organizan su función hash,
si está ordenado, es posible que pueda volver falso un poco antes,
pero si se trata de clasificar, entonces usted quiere seguir recorriendo a través de su lista enlazada
hasta encontrar el último elemento de la lista.
Y si todavía no has encontrado la palabra por el tiempo que has llegado al final de la lista enlazada,
que significa que su palabra no existe en el diccionario,
y para que la palabra no es válido,
y el cheque debe devolver false.
>> Ahora llegamos a la descarga, donde queremos liberar a todos los nodos que hemos malloc'd,
tan libre de todos los nodos dentro de nuestra tabla hash.
Vamos a querer iterar sobre todas las listas enlazadas y libres de todos los nodos en eso.
Si se mira más arriba en el tutorial para el ejemplo en el que liberar a una lista enlazada,
entonces usted querrá repetir este proceso para cada elemento en la tabla hash.
Y voy a ir más de esto hacia el final del tutorial,
pero Valgrind es una herramienta donde se puede ver si se ha liberado correctamente
cada nodo que ha malloc'd o cualquier otra cosa que hayas malloc'd, cualquier otro puntero.
Así que eso es tablas hash, donde tenemos un número finito de cubos
y una función hash que tendrá un valor y asignar ese valor a un cubo determinado.
>> Ahora llegamos a intentos.
Trata tipo de mirada así, y también voy a sacar un ejemplo.
Básicamente, usted tiene toda una serie de cartas posibles,
y entonces cada vez que usted está construyendo una palabra,
carta que pueden enlazarse para un diccionario para una amplia gama de posibilidades.
Algunas palabras comienzan con C, pero luego continuar con A,
pero otros continúan con O, por ejemplo.
Un trie es una manera de visualizar todas las posibles combinaciones de esas palabras.
Un trie se va a realizar un seguimiento de la secuencia de letras que forman las palabras,
ramifica cuando sea necesario, cuando una sola letra puede ser seguido por un múltiplo de cartas,
y al final indican en cada punto si esa palabra es válida o no
porque si usted está deletreando la palabra MAT, MA No creo que es una palabra válida, pero es MAT.
Y así, en el trie, lo que indicaría que, después de MAT que en realidad es una palabra válida.
Cada nodo en nuestro trie es en realidad va a contener una matriz de punteros de nodos,
y vamos a tener, en concreto, 27 de esos punteros a nodos,
una para cada letra del alfabeto, así como el carácter de apóstrofo.
Cada elemento de la matriz se está yendo al punto a otro nodo.
Así que si ese nodo es NULL, si no hay nada después de eso,
entonces sabemos que no hay más cartas en esa secuencia de palabras.
Pero si ese nodo no es NULL, que significa que hay más cartas en que secuencia de letras.
Y además, cada nodo indica si es el último carácter de una palabra o no.
>> Vamos a entrar en un ejemplo de un trie.
Primero tengo espacio para 27 nodos en esta matriz.
Si tengo la palabra BAR -
Si tengo la palabra BAR y quiero insertar en que,
la primera letra es B, así que si mi trie está vacío,
B es la segunda letra del alfabeto, así que voy a optar por poner esto aquí en este índice.
Voy a tener B aquí.
B va a ser un nodo que apunta a otra matriz de todos los personajes posibles
que puede seguir después de la letra B.
En este caso, estoy tratando con la palabra BAR, por lo que A se ve aquí.
Después de una, yo tengo la letra R, por lo que entonces A Puntos ahora para su propia combinación,
y R estarán aquí.
BAR es una palabra completa, entonces yo voy a tener el punto R a otro nodo
que dice que esa palabra es válida.
Ese nodo también va a tener un conjunto de nodos,
pero los que podrían ser NULL.
Pero, básicamente, se puede seguir así.
Eso será un poco más claro cuando vamos a un ejemplo diferente,
así que tengan paciencia conmigo allí.
Ahora tenemos BAR interior de nuestro diccionario.
Ahora digamos que tenemos la palabra BAZ.
Comenzamos con B, y ya tenemos B como una de las letras que hay en nuestro diccionario.
Esto es seguido por A. Tenemos una ya.
Pero en su lugar, tenemos lo siguiente Z.
Así pues, un elemento en nuestra matriz va a ser Z,
y es así, que se va a apuntar a otra final válido de la palabra.
Así vemos que cuando seguimos a través de B y luego A,
hay dos opciones diferentes en la actualidad en nuestro diccionario para las palabras que comienzan con B y A.
Digamos que quería insertar la palabra pepe.
Entonces nos volveríamos a hacer una entrada en F.
F es un nodo que apunta a una matriz completa.
Nos encontraríamos O, vaya a O, O entonces enlaza a una lista completa.
Tendríamos B y continuar luego, tendríamos entonces A y R.
Entonces atraviesa foobar todo el camino hasta FOOBAR es una palabra correcta.
Y así, entonces esto sería una palabra válida.
Ahora que nuestra próxima palabra en el diccionario es en realidad la palabra FOO.
Diríamos F. Lo que sigue a F?
De hecho ya tenemos un espacio para O, así que voy a continuar.
No es necesario hacer una nueva. Continuar.
FOO es una palabra válida en este diccionario, por lo que a continuación voy a indicar
que es válida.
Si dejo mi secuencia allí, que sería correcto.
Pero si continuamos con nuestra secuencia de FOO hasta B
y sólo tenía foob, foob no es una palabra, y eso no es indicado como una válida.
En un trie, tienes todo el nodo que indica si se trata de una palabra válida o no,
y entonces cada nodo también tiene una serie de 27 punteros a nodos
que a continuación punto a nodos en sí mismos.
>> Esta es una manera de cómo es posible que desee definir esto.
Sin embargo, al igual que en el ejemplo de la tabla hash, donde tuvimos un nodo cabeza *
para indicar el comienzo de nuestra lista enlazada, también vamos a querer
alguna manera de saber dónde está el principio de nuestra trie es.
Algunos llaman a la gente trata de árboles, y ahí es donde viene de la raíz.
Así que queremos que la raíz de nuestro árbol para asegurarse de que nos quedamos a tierra
a donde nuestro trie es.
Ya fui tipo de
la forma en que podía pensar en cargar cada palabra en el diccionario.
Esencialmente, por cada palabra que vas a querer recorrer su trie
y sabiendo que todos los elementos de los niños - lo llamamos niños en este caso -
corresponde a una letra diferente, usted va a desear para comprobar los valores
en ese índice en particular que corresponde a la letra.
Así que pensando todo el camino de vuelta a César y Vigenère,
sabiendo que cada letra puede tipo de mapa a un índice alfabético,
Definitivamente la A a la Z va a ser muy fácil de asignar a una letra del alfabeto,
pero, por desgracia, apóstrofos son también un carácter aceptada en palabras.
Ni siquiera estoy seguro de cuál es el valor ASCII es,
por lo que para que si quieres encontrar un índice para decidir si usted quiere que ser el primero
o el último, usted tendrá que hacer un cheque duro codificado para que
y luego poner que en el índice de 26, por ejemplo.
Así que usted está comprobando el valor en los niños [i]
donde [e] corresponde a cualquier carta que usted está en.
Si es NULL, lo que significa que no hay actualmente ningún cartas posibles
derivada de la secuencia anterior, por lo que vas a querer a malloc
y crea un nuevo nodo y que los niños tienen [i] apuntan a que
por lo que cree - cuando inserta una letra en el rectángulo -
hacer que los niños no nulo y el punto en que el nuevo nodo.
Pero si eso no es NULL, como en nuestro ejemplo de FOO
cuando ya teníamos FOOBAR, continuamos,
y no estamos siempre haciendo un nuevo nodo, sino sólo establecer en true is_word
al final de la palabra.
>> Así que, como antes, porque aquí estamos tratando con todas las cartas a la vez,
que va a ser más fácil para usted para el tamaño, en lugar de tener que calcular
y pasar por todo el árbol y calcular cuántos hijos tengo
y luego se ramifica, recordando cuántos están en el lado izquierdo y en el lado derecho
y cosas por el estilo, va a ser mucho más fácil para usted
si usted acaba de hacer un seguimiento de la cantidad de palabras que está añadiendo en
cuando usted está tratando con carga.
Y así, luego de que el tamaño medio sólo puede devolver una variable global de tamaño.
>> Ahora vamos a comprobar.
Mismas normas que antes, en la que desea permitir para que no se distingan.
Además, se supone que las cadenas son caracteres alfabéticos o apóstrofos sólo los
porque los niños es una matriz de 27 de largo,
así que todas las letras del alfabeto más el apóstrofe.
Para comprobar lo que usted querrá hacer es que usted querrá empezar en la raíz
porque la raíz se apuntan a una matriz que contiene
todas las cartas posibles a partir de una palabra.
Vas a empezar por ahí,
y entonces usted va a comprobar es el valor NULL o no,
porque si el valor es NULL, que significa que el diccionario no tiene ningún valor
que contiene esa carta en ese orden particular.
Si es NULL, entonces eso significa que la palabra está mal escrita en seguida.
Pero si no es NULL, entonces usted puede continuar,
decir que la primera letra es una letra posible por primera vez en una palabra,
por lo que ahora quiero comprobar si la segunda letra, esa secuencia, está en mi diccionario.
Así que vamos a ir al índice de los hijos del primer nodo
y comprobar si esa segunda carta existe.
A continuación, repita este proceso para comprobar si esa secuencia es válida o no
dentro de su trie.
Cada vez que los niños de nodo en que los puntos de índice en NULL,
Sabe usted que esa secuencia no existe,
pero si se llega al final de la palabra que ha introducido,
entonces usted quiere comprobar ahora que he terminado esta secuencia
y se encontró en medio de mi trie, es esa palabra válida o no?
Y entonces usted quiere comprobar esto, y es que cuando si has encontrado esa secuencia,
entonces usted quiere comprobar si esa palabra es válida o no
porque recuerdo que en el caso anterior que dibujé donde tuvimos foob,
que era una secuencia válida que hemos encontrado, pero no era una palabra real válido en sí.
>> Del mismo modo, para descargar en los intentos que desea descargar todos los nodos del trie.
Lo siento. Similar a las tablas hash en donde descargar liberamos todos los nodos,
en los intentos que queremos liberar también a todos los nodos.
Descargue en realidad será más fácil trabajar de abajo hacia arriba
porque son esencialmente las listas enlazadas.
Así que queremos asegurarnos de que nos aferramos a todos los valores
y libre de todos ellos de forma explícita.
¿Qué vas a querer hacer si usted está trabajando con un trie
es viajar a la parte inferior y libre en el nodo más bajo posible en primer lugar
y luego ir a todos esos niños y luego liberar a todos aquellos,
subir, etc, entonces libre
Tipo de como tratar con la capa inferior de la primera trie
y luego ir hasta la parte superior una vez que haya liberado todo.
Este es un buen ejemplo de que la función recursiva puede ser útil.
Una vez que haya liberado la capa inferior de su trie,
luego se llama a descargar sobre el resto de la misma,
asegurándose de liberar a todos los mini -
Puedes tipo de visualizarlo como intentos mini.
Así que tiene su raíz aquí.
Yo sólo lo estoy simplificando así que no tienes que dibujar 26 de ellos.
Así que los tiene, y entonces éstos representan secuencias de palabras
donde todos estos pequeños círculos son letras que son secuencias válidas de cartas.
Vamos a seguir un poco más.
¿Qué vas a querer hacer es liberar el fondo aquí y luego liberar esta
y entonces libre este en la parte inferior antes de liberar la parte superior hasta aquí
porque si algo libre en el segundo nivel aquí,
entonces usted realmente perder este valor aquí.
Es por eso que es importante para descargar en un trie para asegurarse de que usted libere la parte inferior primero.
Lo que usted puede ser que desee hacer es decir por cada nodo
Quiero descargar todo de los niños.
>> Ahora que hemos repasado descargar para el método de tabla hash, así como el método trie,
vamos a querer mirar Valgrind.
Valgrind se ejecuta con los siguientes comandos.
Usted tiene valgrind-v.
Estás comprobación de todas las fugas cuando se ejecuta speller dado este texto determinado
porque ortografía tiene que tomar en un archivo de texto.
Así Valgrind ejecutará el programa, le dirá la cantidad de bytes que asigna,
cantidad de bytes que liberó, y ella le dirá si usted liberado lo suficiente
o si usted no lo hizo lo suficientemente libre,
o, a veces incluso se puede sobre-libre, libre como un nodo que ya ha sido liberado
y por lo que le devuelven errores.
Si utiliza Valgrind, que le dará algunos mensajes
indica si se ha liberado ni menos que suficiente, lo suficiente,
o más de lo suficiente.
>> Una parte de este conjunto de procesadores, es opcional para desafiar a la Junta Grande.
Pero cuando nos enfrentamos a estas estructuras de datos
es una especie de divertido ver la rapidez y la eficiencia de sus estructuras de datos podría ser.
¿Su resultado de la función hash en una gran cantidad de colisiones?
¿O es su tamaño de datos muy grande?
¿Se necesita mucho tiempo para recorrer?
En el registro de ortografía, nos devuelve la cantidad de tiempo que se utiliza para cargar,
para comprobar, para llevar a cabo tamaño, y descargar a,
y por lo que aquellos se publican en la Bolsa de Nueva York,
donde puedes competir contra tus compañeros de clase
y algunos miembros del personal para ver quién tiene el más rápido corrector ortográfico.
Una cosa que me gustaría destacar sobre las tablas hash
es que hay algunas funciones hash bastante simples que podríamos imaginar.
Por ejemplo, tienes 26 cubos, y así cada cubo
corresponde a la primera letra de una palabra,
pero eso va a resultar en una tabla hash bastante desequilibrada
porque hay muchas menos palabras que comienzan con X que comienza con M, por ejemplo.
Una manera de ir sobre la ortografía es si usted desea obtener toda la funcionalidad de otro hacia abajo,
a continuación, sólo tiene que utilizar una función hash simple para ser capaz de obtener su código que se ejecuta
y después volver atrás y cambiar el tamaño de la tabla hash y la definición.
Hay un montón de recursos en Internet para las funciones hash,
por lo que para este conjunto de procesadores se le permite investigar las funciones de hash en Internet
para algunos consejos e inspiración, siempre y cuando, es imprescindible citar dónde lo obtuvo.
Le invitamos a mirar e interpretar una función hash que usted encuentra en el Internet.
Volver a eso, usted podría ser capaz de ver si alguien utiliza un trie
si su aplicación es más rápida que la tabla hash o no.
Usted puede presentar a la Bolsa de Nueva York varias veces.
Se registrará su entrada más reciente.
Así que tal vez cambie su función de control y luego darse cuenta de que en realidad es mucho más rápido
o mucho más lento que antes.
Eso es un poco de una forma divertida.
Siempre hay uno o dos miembros del personal que tratan de hacer que el diccionario más lento posible,
por lo que siempre es divertido para mirar.
>> El uso para el conjunto de procesadores se ejecuta con un diccionario ortográfico opcional
y a continuación, un archivo de texto obligatorio.
De forma predeterminada cuando se ejecuta abecedario con sólo un archivo de texto y no se especifica un diccionario,
que va a utilizar el archivo de texto diccionario, el grande
en la carpeta cs50/pset5/dictionaries.
Que uno tiene más de 100.000 palabras.
También tienen un pequeño diccionario de palabras que tiene considerablemente menos
CS50 que ha hecho para ti.
Sin embargo, puede muy fácilmente con sólo hacer su propio diccionario
si lo que desea es estar trabajando en pequeños ejemplos -
por ejemplo, si desea utilizar gdb y usted sabe los valores específicos
que desea que la tabla hash para mapear a.
Por lo que sólo puede hacer su propio archivo de texto sólo con BAR, BAZ, FOO, y FOOBAR,
hacen que en un archivo de texto, separe cada uno con los que 1 línea,
y luego hacer su propio archivo de texto que contiene, literalmente, sólo tal vez 1 o 2 palabras
para que usted sepa exactamente lo que el resultado debería ser.
Algunos de los archivos de texto que muestra la Bolsa de Nueva York cuando se ejecuta reto comprobará
son Guerra y Paz y una novela de Jane Austen o algo por el estilo.
Así que cuando estás empezando, es mucho más fácil de hacer sus propios archivos de texto
que contienen sólo un par de palabras, o tal vez 10
por lo que se puede predecir cuál será el resultado debe ser
y luego compárelo con eso, así que más de un ejemplo controlado.
Y ya que estamos tratando con la predicción y el dibujo las cosas,
más quiero animaros a utilizar lápiz y papel
porque es realmente va a ayudar con esto -
dibujar las flechas, cómo la tabla hash o cómo se ve tu trie,
cuando estás liberando algo donde las flechas van,
lo llevas a poco, ve usted ningún enlace desapareciendo
y caer en el abismo de la memoria perdida.
Así que por favor, por favor, trate de sacar las cosas incluso antes de llegar a escribir código abajo.
Dibuja las cosas para que pueda entender cómo las cosas van a trabajar
porque entonces te garantizo que te encuentres a confusiones puntero menos allí.
>> Está bien.
Quiero desearle la mejor de las suertes con este conjunto de procesadores.
Es probablemente el más difícil.
Así que trate de empezar pronto, dibujar las cosas, sacar las cosas, y buena suerte.
Esto era Tutorial 5.
>> [CS50.TV]