DOUG LLOYD: Así que en CS50, hemos cubierto un montón de diferentes estructuras de datos, ¿derecho? Hemos visto las matrices, y vinculados listas y tablas hash, y tries, pilas y colas. También aprenderemos un poco sobre los árboles y montones, pero en realidad todos estos simplemente terminan siendo hasta variaciones sobre un tema. Realmente es esto tipo de cuatro ideas básicas que todo lo demás se reducen a. Arrays, listas enlazadas, tablas hash y tries. Y como he dicho, no son variaciones sobre ellos, pero esto es bastante hay mucho que hacer para resumir todo lo que vamos a hablar acerca de esta clase en términos de C. Pero, ¿cómo hacen éstos de toda medida, ¿no? Hemos hablado acerca de los pros y los contras de cada uno en vídeos separados sobre ellos, pero hay un montón de números siendo lanzado alrededor. Hay una gran cantidad de generales pensamientos conseguir lanzados alrededor. Vamos a tratar de consolidar en un solo lugar. Vamos a sopesar los pros contra los contras, y consideran que la estructura de datos podrían ser los datos correctos estructura para su situación particular, cualquier tipo de datos que se está almacenando. No necesariamente siempre hay que utilizar la inserción super rápido, eliminación, y la búsqueda de un trie si realmente no se preocupan por la inserción y eliminación demasiado. Si usted necesita apenas rápidamente al azar el acceso, puede que un arreglo es mejor. Así que vamos a destilar eso. Vamos a hablar de cada uno de los cuatro principales tipos de estructuras de datos que hemos hablado, y simplemente ver cuando puede ser bueno, y cuando ellos podrían no ser tan bueno. Así que vamos a empezar con las matrices. Así inserción, eso es algo malo. 

La inserción en el final de una matriz está bien, si estamos construyendo un arsenal a medida que avanzamos. Pero si tenemos que insertar elementos en el medio, pensar de nuevo a la inserción especie, hay mucho de cambiar para adaptarse a un elemento en ese país. Y por lo que si vamos a insertar en cualquier lugar, pero el final de una matriz, no creo que sea tan grande. 

Del mismo modo, la supresión, a menos que estemos borrar desde el final de una matriz, es probable que también no tan grande si no queremos dejar espacios vacíos, que por lo general no lo hacemos. Queremos eliminar un elemento, y entonces especie de que sea ajustado de nuevo. Y así la supresión de elementos de una matriz, también no tan grande. 

Operaciones de búsqueda, sin embargo, es grande. Tenemos acceso aleatorio, búsqueda constante de tiempo. Acabamos de decir siete, y nos vamos a la reubicación serie de siete. Decimos 20, a la cita de reubicación serie 20. Nosotros no tenemos que recorrer a través. Eso es bastante bueno. 

Las matrices también son relativamente fáciles de resolver. Cada vez que hablamos de una clasificación algoritmo, como la selección de género, ordenación por inserción, ordenamiento de burbuja, fusionar especie, siempre utilizamos matrices para hacerlo, porque las matrices son bastante fáciles de especie, con relación a las estructuras de datos que hemos visto hasta ahora. 

También son relativamente pequeñas. No hay un montón de espacio extra. Usted acaba de dejar de lado exactamente tanto como sea necesario para mantener sus datos, Y eso es todo. Así que son bastante pequeñas y eficiente de esa manera. Pero otro aspecto negativo, sin embargo, es que están fijos en tamaño. Tenemos que declarar exactamente cómo gran Queremos que nuestra matriz a ser, y sólo tenemos una oportunidad. No podemos crecer y reducir su tamaño. 

Si necesitamos para crecer o encoger, nos tenga que declarar una matriz totalmente nuevo, copiar todos los elementos de la primera matriz en la segunda matriz. Y si calculamos mal que tiempo, tenemos que hacerlo de nuevo. No muy bien. Así matrices no nos dan la flexibilidad tener un número variable de elementos. 

Con una lista enlazada, la inserción es bastante fácil. Acabamos de virar hacia el frente. Supresión también es bastante fácil. Tenemos que encontrar los elementos. Que implican algunas búsquedas. 

Pero una vez que haya encontrado el elemento que estás buscando, todo lo que tiene que hacer es cambiar un puntero, posiblemente dos si tiene una vinculada películas-- un doble lista enlazada, rather-- y entonces usted puede simplemente liberar el nodo. Usted no tiene que cambiar todo a su alrededor. Usted acaba de cambiar dos punteros, así que eso es bastante rápido. 

Operaciones de búsqueda es malo, ¿verdad? Con el fin para nosotros encontrar un elemento de una lista enlazada, ya sea individualmente o doblemente enlazada, tenemos que buscarla en el lineal. Tenemos que empezar por el principio y mover el extremo, o empezar por el movimiento final Al Principio. No tenemos acceso aleatorio más. Así que si estamos haciendo un montón de búsqueda, tal vez una lista enlazada no es tan bueno para nosotros. 

También son muy difícil de resolver, ¿verdad? La única manera de que pueda realmente ordenar una lista enlazada es para solucionar el problema a medida que construyes él. Pero si ordena como usted construirlo, ya no estás haciendo inserciones rápidas más. Usted no está solo viradas cosas en la parte frontal. Tienes que encontrar la lugar adecuado para decirlo, y luego su inserción se vuelve casi tan malo como la inserción en una matriz. Así listas enlazadas no son tan grande para la clasificación de datos. 

También son bastante pequeñas, de tamaño conveniente. Lista doblemente enlazada ligeramente más grande que las listas por separado enlazados, que son ligeramente más grandes de matrices, pero no es una enorme cantidad de espacio desperdiciado. Así que si el espacio es un bien escaso, pero no una prima muy intenso, este podría ser el camino correcto a seguir. 

Las tablas hash. La inserción en una tabla hash es bastante sencillo. Es un proceso de dos pasos. En primer lugar tenemos que correr a través de nuestros datos una función hash para obtener un código hash, y luego insertamos el elemento en el tabla hash en esa ubicación código hash. 

Supresión, similar a la lista enlazada, es fácil una vez que encuentre el elemento. Tienes que encontrarlo primero, pero luego, cuando lo elimina, sólo tiene que intercambiar un par de punteros, si usted está utilizando encadenamiento separado. Si estás usando el sondeo, o si no estás utilizando el encadenamiento en absoluto en su tabla hash, eliminación es realmente muy fácil. Todo lo que necesitas hacer es hash de la de datos y, a continuación, ir a ese lugar. Y suponiendo que no lo hace tener colisiones, podrás eliminar rápidamente. 

Ahora, la búsqueda es donde las cosas ser un poco más complicado. Está en medio de una mejor de listas enlazadas. Si está utilizando el encadenamiento, todavía tiene una lista enlazada, lo que significa que todavía tiene la Búsqueda cause un perjuicio una lista enlazada. Pero debido a que usted está tomando su ligados lista y su división de más de 100 o 1000 o n elementos en su tabla hash, eres listas enlazadas son todos uno enésimo el tamaño. Todos son sustancialmente menor. Has n vinculados listas vez de una sola lista enlazada de tamaño n. 

Y por lo que este mundo real constante factor, que por lo general, no se habla de la complejidad tiempo, no realmente hacer una diferencia aquí. Así de búsqueda sigue siendo lineal buscar si usted está utilizando el encadenamiento, pero la longitud de la lista Estás en la es muy, muy corto en comparación. De nuevo, si la clasificación es su objetivo aquí, tabla hash de probablemente no es el camino correcto a seguir. Sólo tiene que utilizar una matriz si la clasificación es realmente importante para usted. 

Y pueden funcionar la gama de tamaño. Es difícil decir si un tabla hash es pequeño o grande, porque realmente depende de el tamaño de su tabla hash es. Si sólo vas a almacenar cinco elementos en su tabla hash, y usted tiene una tabla hash con 10.000 elementos en los mismos, te estás perdiendo un montón de espacio. Contraste ser que también puedes tiene tablas hash muy compactas, pero el más pequeño de su tabla hash se pone, cuanto más tiempo cada una de esas listas enlazadas consigue. Y así, no hay realmente ninguna manera de definir exactamente el tamaño de una tabla hash, pero es probablemente seguro decir que es por lo general va a ser más grande que una vinculada Lista de almacenamiento de los mismos datos, pero más pequeño que un trie. 

Y intentos son la cuarta de estas estructuras que hemos estado hablando. Inserción en un trie es compleja. Hay un montón de dinámica asignación de memoria, sobre todo al principio, como vas a empezar a construir. Pero es tiempo constante. No es más que el elemento humano aquí que hace que sea difícil. Tener que encontrar puntero nulo, malloc espacio, ir allí, el espacio, posiblemente malloc desde allí de nuevo. El tipo de factor de intimidación de punteros en la asignación de memoria dinámica es el obstáculo para borrar. Pero una vez que haya limpiado ella, la inserción en realidad viene muy simple, y sin duda es la constante de tiempo. 

Supresión es fácil. Todo lo que necesitas hacer es navegar por una par de punteros y conexión al nodo, así que eso es bastante bueno. Operaciones de búsqueda también es bastante rápido. Sólo se basa en la longitud de sus datos. Así que si todos sus datos es cinco cadenas de caracteres, por ejemplo, usted está almacenando de cinco cadenas de caracteres en el trie, sólo se tarda cinco pasos para encontrar lo que estás buscando. El cinco es sólo un factor constante, por lo que de nuevo, la inserción, eliminación y búsqueda aquí están todos los tiempos constante, eficaz. 

Otra cosa es que su trie es en realidad un poco ya ordenados, ¿verdad? En virtud de lo que somos elementos de inserción, yendo letra por letra del clave, o dígito a dígito de la clave, normalmente, su trie termina siendo tipo de ordenados como lo construyes. En realidad no hace sentido de pensar en la clasificación de la misma manera en que pensamos acerca con matrices o listas enlazadas, o tablas hash. Pero en cierto sentido, su trie está ordenada a medida que avanza. 

La desventaja, por supuesto, es que un trie se convierte rápidamente en enormes. Desde todos los puntos de unión, es posible que tener-- si su clave consiste en dígitos, usted tiene 10 otra lugares a los que pueden ir, que significa que cada nodo contiene información acerca de los datos que desea almacenar en ese nodo, más 10 puntos. Lo cual, en CS50 IDE, es de 80 bytes. Así que es por lo menos 80 bytes para cada nodo que se crea, y eso sin contar los datos. Y si sus nodos son letras en vez de números, ahora tienes 26 punteros de cada lugar. Y 26 veces 8 es probablemente 200 bytes, o algo así. Y usted tiene el capital y usted puede lowercase-- ver dónde voy con esto, ¿verdad? Sus nodos pueden conseguir realmente grande, y por lo que el trie sí, en general, puede conseguir realmente grande, demasiado. Así que si el espacio es muy alta prima en su sistema, un trie vez no sea la manera correcta de vaya, a pesar de que sus otros beneficios ven a jugar. Soy Doug Lloyd. Esto es CS50.