1 00:00:00,000 --> 00:00:05,259 2 00:00:05,259 --> 00:00:08,300 DOUG LLOYD: Así que en CS50, hemos cubierto un montón de diferentes estructuras de datos, 3 00:00:08,300 --> 00:00:09,180 ¿derecho? 4 00:00:09,180 --> 00:00:11,420 Hemos visto las matrices, y vinculados listas y tablas hash, 5 00:00:11,420 --> 00:00:15,210 y tries, pilas y colas. 6 00:00:15,210 --> 00:00:17,579 También aprenderemos un poco sobre los árboles y montones, 7 00:00:17,579 --> 00:00:20,120 pero en realidad todos estos simplemente terminan siendo hasta variaciones sobre un tema. 8 00:00:20,120 --> 00:00:22,840 Realmente es esto tipo de cuatro ideas básicas 9 00:00:22,840 --> 00:00:25,190 que todo lo demás se reducen a. 10 00:00:25,190 --> 00:00:28,150 Arrays, listas enlazadas, tablas hash y tries. 11 00:00:28,150 --> 00:00:30,720 Y como he dicho, no son variaciones sobre ellos, 12 00:00:30,720 --> 00:00:32,720 pero esto es bastante hay mucho que hacer para resumir 13 00:00:32,720 --> 00:00:38,140 todo lo que vamos a hablar acerca de esta clase en términos de C. 14 00:00:38,140 --> 00:00:40,140 >> Pero, ¿cómo hacen éstos de toda medida, ¿no? 15 00:00:40,140 --> 00:00:44,265 Hemos hablado acerca de los pros y los contras de cada uno en vídeos separados sobre ellos, 16 00:00:44,265 --> 00:00:46,390 pero hay un montón de números siendo lanzado alrededor. 17 00:00:46,390 --> 00:00:48,723 Hay una gran cantidad de generales pensamientos conseguir lanzados alrededor. 18 00:00:48,723 --> 00:00:51,950 Vamos a tratar de consolidar en un solo lugar. 19 00:00:51,950 --> 00:00:55,507 Vamos a sopesar los pros contra los contras, y consideran 20 00:00:55,507 --> 00:00:57,340 que la estructura de datos podrían ser los datos correctos 21 00:00:57,340 --> 00:01:01,440 estructura para su situación particular, cualquier tipo de datos que se está almacenando. 22 00:01:01,440 --> 00:01:06,625 No necesariamente siempre hay que utilizar la inserción super rápido, eliminación, 23 00:01:06,625 --> 00:01:10,761 y la búsqueda de un trie si realmente no se preocupan por la inserción y eliminación 24 00:01:10,761 --> 00:01:11,260 demasiado. 25 00:01:11,260 --> 00:01:13,968 Si usted necesita apenas rápidamente al azar el acceso, puede que un arreglo es mejor. 26 00:01:13,968 --> 00:01:15,340 Así que vamos a destilar eso. 27 00:01:15,340 --> 00:01:18,530 Vamos a hablar de cada uno de los cuatro principales tipos de estructuras de datos 28 00:01:18,530 --> 00:01:21,720 que hemos hablado, y simplemente ver cuando puede ser bueno, 29 00:01:21,720 --> 00:01:23,340 y cuando ellos podrían no ser tan bueno. 30 00:01:23,340 --> 00:01:24,610 Así que vamos a empezar con las matrices. 31 00:01:24,610 --> 00:01:27,300 Así inserción, eso es algo malo. 32 00:01:27,300 --> 00:01:31,350 >> La inserción en el final de una matriz está bien, si estamos construyendo un arsenal a medida que avanzamos. 33 00:01:31,350 --> 00:01:33,570 Pero si tenemos que insertar elementos en el medio, 34 00:01:33,570 --> 00:01:35,550 pensar de nuevo a la inserción especie, hay mucho 35 00:01:35,550 --> 00:01:37,510 de cambiar para adaptarse a un elemento en ese país. 36 00:01:37,510 --> 00:01:41,170 Y por lo que si vamos a insertar en cualquier lugar, pero el final de una matriz, 37 00:01:41,170 --> 00:01:43,590 no creo que sea tan grande. 38 00:01:43,590 --> 00:01:46,710 >> Del mismo modo, la supresión, a menos que estemos borrar desde el final de una matriz, 39 00:01:46,710 --> 00:01:49,810 es probable que también no tan grande si no queremos dejar espacios vacíos, 40 00:01:49,810 --> 00:01:50,790 que por lo general no lo hacemos. 41 00:01:50,790 --> 00:01:54,700 Queremos eliminar un elemento, y entonces especie de que sea ajustado de nuevo. 42 00:01:54,700 --> 00:01:57,670 Y así la supresión de elementos de una matriz, también no tan grande. 43 00:01:57,670 --> 00:01:58,820 >> Operaciones de búsqueda, sin embargo, es grande. 44 00:01:58,820 --> 00:02:00,920 Tenemos acceso aleatorio, búsqueda constante de tiempo. 45 00:02:00,920 --> 00:02:03,800 Acabamos de decir siete, y nos vamos a la reubicación serie de siete. 46 00:02:03,800 --> 00:02:05,907 Decimos 20, a la cita de reubicación serie 20. 47 00:02:05,907 --> 00:02:07,240 Nosotros no tenemos que recorrer a través. 48 00:02:07,240 --> 00:02:08,630 Eso es bastante bueno. 49 00:02:08,630 --> 00:02:11,020 >> Las matrices también son relativamente fáciles de resolver. 50 00:02:11,020 --> 00:02:14,040 Cada vez que hablamos de una clasificación algoritmo, como la selección de género, 51 00:02:14,040 --> 00:02:18,820 ordenación por inserción, ordenamiento de burbuja, fusionar especie, siempre utilizamos matrices para hacerlo, 52 00:02:18,820 --> 00:02:21,860 porque las matrices son bastante fáciles de especie, con relación a las estructuras de datos 53 00:02:21,860 --> 00:02:22,970 que hemos visto hasta ahora. 54 00:02:22,970 --> 00:02:24,320 >> También son relativamente pequeñas. 55 00:02:24,320 --> 00:02:25,695 No hay un montón de espacio extra. 56 00:02:25,695 --> 00:02:29,210 Usted acaba de dejar de lado exactamente tanto como sea necesario para mantener sus datos, 57 00:02:29,210 --> 00:02:30,320 Y eso es todo. 58 00:02:30,320 --> 00:02:33,180 Así que son bastante pequeñas y eficiente de esa manera. 59 00:02:33,180 --> 00:02:36,000 Pero otro aspecto negativo, sin embargo, es que están fijos en tamaño. 60 00:02:36,000 --> 00:02:38,630 Tenemos que declarar exactamente cómo gran Queremos que nuestra matriz a ser, 61 00:02:38,630 --> 00:02:39,940 y sólo tenemos una oportunidad. 62 00:02:39,940 --> 00:02:41,280 No podemos crecer y reducir su tamaño. 63 00:02:41,280 --> 00:02:44,582 >> Si necesitamos para crecer o encoger, nos tenga que declarar una matriz totalmente nuevo, 64 00:02:44,582 --> 00:02:47,750 copiar todos los elementos de la primera matriz en la segunda matriz. 65 00:02:47,750 --> 00:02:51,410 Y si calculamos mal que tiempo, tenemos que hacerlo de nuevo. 66 00:02:51,410 --> 00:02:52,760 No muy bien. 67 00:02:52,760 --> 00:02:58,750 Así matrices no nos dan la flexibilidad tener un número variable de elementos. 68 00:02:58,750 --> 00:03:01,320 >> Con una lista enlazada, la inserción es bastante fácil. 69 00:03:01,320 --> 00:03:03,290 Acabamos de virar hacia el frente. 70 00:03:03,290 --> 00:03:04,892 Supresión también es bastante fácil. 71 00:03:04,892 --> 00:03:06,100 Tenemos que encontrar los elementos. 72 00:03:06,100 --> 00:03:07,270 Que implican algunas búsquedas. 73 00:03:07,270 --> 00:03:10,270 >> Pero una vez que haya encontrado el elemento que estás buscando, todo lo que tiene que hacer 74 00:03:10,270 --> 00:03:12,830 es cambiar un puntero, posiblemente dos si tiene 75 00:03:12,830 --> 00:03:15,151 una vinculada películas-- un doble lista enlazada, rather-- 76 00:03:15,151 --> 00:03:16,650 y entonces usted puede simplemente liberar el nodo. 77 00:03:16,650 --> 00:03:18,399 Usted no tiene que cambiar todo a su alrededor. 78 00:03:18,399 --> 00:03:22,090 Usted acaba de cambiar dos punteros, así que eso es bastante rápido. 79 00:03:22,090 --> 00:03:23,470 >> Operaciones de búsqueda es malo, ¿verdad? 80 00:03:23,470 --> 00:03:26,280 Con el fin para nosotros encontrar un elemento de una lista enlazada, 81 00:03:26,280 --> 00:03:29,154 ya sea individualmente o doblemente enlazada, tenemos que buscarla en el lineal. 82 00:03:29,154 --> 00:03:32,320 Tenemos que empezar por el principio y mover el extremo, o empezar por el movimiento final 83 00:03:32,320 --> 00:03:33,860 Al Principio. 84 00:03:33,860 --> 00:03:35,474 No tenemos acceso aleatorio más. 85 00:03:35,474 --> 00:03:37,265 Así que si estamos haciendo un montón de búsqueda, tal vez 86 00:03:37,265 --> 00:03:39,830 una lista enlazada no es tan bueno para nosotros. 87 00:03:39,830 --> 00:03:43,750 >> También son muy difícil de resolver, ¿verdad? 88 00:03:43,750 --> 00:03:45,666 La única manera de que pueda realmente ordenar una lista enlazada 89 00:03:45,666 --> 00:03:47,870 es para solucionar el problema a medida que construyes él. 90 00:03:47,870 --> 00:03:50,497 Pero si ordena como usted construirlo, ya no estás 91 00:03:50,497 --> 00:03:51,830 haciendo inserciones rápidas más. 92 00:03:51,830 --> 00:03:53,746 Usted no está solo viradas cosas en la parte frontal. 93 00:03:53,746 --> 00:03:55,710 Tienes que encontrar la lugar adecuado para decirlo, 94 00:03:55,710 --> 00:03:57,820 y luego su inserción se vuelve casi tan malo 95 00:03:57,820 --> 00:03:59,390 como la inserción en una matriz. 96 00:03:59,390 --> 00:04:03,130 Así listas enlazadas no son tan grande para la clasificación de datos. 97 00:04:03,130 --> 00:04:05,830 >> También son bastante pequeñas, de tamaño conveniente. 98 00:04:05,830 --> 00:04:08,496 Lista doblemente enlazada ligeramente más grande que las listas por separado enlazados, 99 00:04:08,496 --> 00:04:10,620 que son ligeramente más grandes de matrices, pero no es 100 00:04:10,620 --> 00:04:13,330 una enorme cantidad de espacio desperdiciado. 101 00:04:13,330 --> 00:04:18,730 Así que si el espacio es un bien escaso, pero no una prima muy intenso, 102 00:04:18,730 --> 00:04:22,180 este podría ser el camino correcto a seguir. 103 00:04:22,180 --> 00:04:23,330 >> Las tablas hash. 104 00:04:23,330 --> 00:04:25,850 La inserción en una tabla hash es bastante sencillo. 105 00:04:25,850 --> 00:04:26,980 Es un proceso de dos pasos. 106 00:04:26,980 --> 00:04:30,700 En primer lugar tenemos que correr a través de nuestros datos una función hash para obtener un código hash, 107 00:04:30,700 --> 00:04:37,550 y luego insertamos el elemento en el tabla hash en esa ubicación código hash. 108 00:04:37,550 --> 00:04:40,879 >> Supresión, similar a la lista enlazada, es fácil una vez que encuentre el elemento. 109 00:04:40,879 --> 00:04:43,170 Tienes que encontrarlo primero, pero luego, cuando lo elimina, 110 00:04:43,170 --> 00:04:45,128 sólo tiene que intercambiar un par de punteros, 111 00:04:45,128 --> 00:04:47,250 si usted está utilizando encadenamiento separado. 112 00:04:47,250 --> 00:04:49,942 Si estás usando el sondeo, o si no estás 113 00:04:49,942 --> 00:04:51,650 utilizando el encadenamiento en absoluto en su tabla hash, 114 00:04:51,650 --> 00:04:53,040 eliminación es realmente muy fácil. 115 00:04:53,040 --> 00:04:57,134 Todo lo que necesitas hacer es hash de la de datos y, a continuación, ir a ese lugar. 116 00:04:57,134 --> 00:04:58,925 Y suponiendo que no lo hace tener colisiones, 117 00:04:58,925 --> 00:05:01,650 podrás eliminar rápidamente. 118 00:05:01,650 --> 00:05:04,930 >> Ahora, la búsqueda es donde las cosas ser un poco más complicado. 119 00:05:04,930 --> 00:05:06,910 Está en medio de una mejor de listas enlazadas. 120 00:05:06,910 --> 00:05:09,560 Si está utilizando el encadenamiento, todavía tiene una lista enlazada, 121 00:05:09,560 --> 00:05:13,170 lo que significa que todavía tiene la Búsqueda cause un perjuicio una lista enlazada. 122 00:05:13,170 --> 00:05:18,390 Pero debido a que usted está tomando su ligados lista y su división de más de 100 o 1000 123 00:05:18,390 --> 00:05:25,380 o n elementos en su tabla hash, eres listas enlazadas son todos uno enésimo el tamaño. 124 00:05:25,380 --> 00:05:27,650 Todos son sustancialmente menor. 125 00:05:27,650 --> 00:05:32,080 Has n vinculados listas vez de una sola lista enlazada de tamaño n. 126 00:05:32,080 --> 00:05:34,960 >> Y por lo que este mundo real constante factor, que por lo general, 127 00:05:34,960 --> 00:05:39,730 no se habla de la complejidad tiempo, no realmente hacer una diferencia aquí. 128 00:05:39,730 --> 00:05:43,020 Así de búsqueda sigue siendo lineal buscar si usted está utilizando el encadenamiento, 129 00:05:43,020 --> 00:05:46,780 pero la longitud de la lista Estás en la 130 00:05:46,780 --> 00:05:50,080 es muy, muy corto en comparación. 131 00:05:50,080 --> 00:05:52,995 De nuevo, si la clasificación es su objetivo aquí, tabla hash de 132 00:05:52,995 --> 00:05:54,370 probablemente no es el camino correcto a seguir. 133 00:05:54,370 --> 00:05:56,830 Sólo tiene que utilizar una matriz si la clasificación es realmente importante para usted. 134 00:05:56,830 --> 00:05:58,590 >> Y pueden funcionar la gama de tamaño. 135 00:05:58,590 --> 00:06:01,640 Es difícil decir si un tabla hash es pequeño o grande, 136 00:06:01,640 --> 00:06:04,110 porque realmente depende de el tamaño de su tabla hash es. 137 00:06:04,110 --> 00:06:07,340 Si sólo vas a almacenar cinco elementos en su tabla hash, 138 00:06:07,340 --> 00:06:10,620 y usted tiene una tabla hash con 10.000 elementos en los mismos, 139 00:06:10,620 --> 00:06:12,614 te estás perdiendo un montón de espacio. 140 00:06:12,614 --> 00:06:15,030 Contraste ser que también puedes tiene tablas hash muy compactas, 141 00:06:15,030 --> 00:06:18,720 pero el más pequeño de su tabla hash se pone, cuanto más tiempo cada una de esas listas enlazadas 142 00:06:18,720 --> 00:06:19,220 consigue. 143 00:06:19,220 --> 00:06:22,607 Y así, no hay realmente ninguna manera de definir exactamente el tamaño de una tabla hash, 144 00:06:22,607 --> 00:06:24,440 pero es probablemente seguro decir que es por lo general 145 00:06:24,440 --> 00:06:27,990 va a ser más grande que una vinculada Lista de almacenamiento de los mismos datos, 146 00:06:27,990 --> 00:06:30,400 pero más pequeño que un trie. 147 00:06:30,400 --> 00:06:32,720 >> Y intentos son la cuarta de estas estructuras 148 00:06:32,720 --> 00:06:34,070 que hemos estado hablando. 149 00:06:34,070 --> 00:06:36,450 Inserción en un trie es compleja. 150 00:06:36,450 --> 00:06:38,400 Hay un montón de dinámica asignación de memoria, 151 00:06:38,400 --> 00:06:40,780 sobre todo al principio, como vas a empezar a construir. 152 00:06:40,780 --> 00:06:43,700 Pero es tiempo constante. 153 00:06:43,700 --> 00:06:47,690 No es más que el elemento humano aquí que hace que sea difícil. 154 00:06:47,690 --> 00:06:53,250 Tener que encontrar puntero nulo, malloc espacio, ir allí, el espacio, posiblemente malloc 155 00:06:53,250 --> 00:06:54,490 desde allí de nuevo. 156 00:06:54,490 --> 00:06:58,880 El tipo de factor de intimidación de punteros en la asignación de memoria dinámica 157 00:06:58,880 --> 00:07:00,130 es el obstáculo para borrar. 158 00:07:00,130 --> 00:07:04,550 Pero una vez que haya limpiado ella, la inserción en realidad viene muy simple, 159 00:07:04,550 --> 00:07:06,810 y sin duda es la constante de tiempo. 160 00:07:06,810 --> 00:07:07,680 >> Supresión es fácil. 161 00:07:07,680 --> 00:07:11,330 Todo lo que necesitas hacer es navegar por una par de punteros y conexión al nodo, 162 00:07:11,330 --> 00:07:12,420 así que eso es bastante bueno. 163 00:07:12,420 --> 00:07:13,930 Operaciones de búsqueda también es bastante rápido. 164 00:07:13,930 --> 00:07:16,780 Sólo se basa en la longitud de sus datos. 165 00:07:16,780 --> 00:07:19,924 Así que si todos sus datos es cinco cadenas de caracteres, 166 00:07:19,924 --> 00:07:22,590 por ejemplo, usted está almacenando de cinco cadenas de caracteres en el trie, 167 00:07:22,590 --> 00:07:25,439 sólo se tarda cinco pasos para encontrar lo que estás buscando. 168 00:07:25,439 --> 00:07:28,480 El cinco es sólo un factor constante, por lo que de nuevo, la inserción, eliminación y búsqueda 169 00:07:28,480 --> 00:07:31,670 aquí están todos los tiempos constante, eficaz. 170 00:07:31,670 --> 00:07:34,880 >> Otra cosa es que su trie es en realidad un poco ya ordenados, ¿verdad? 171 00:07:34,880 --> 00:07:36,800 En virtud de lo que somos elementos de inserción, 172 00:07:36,800 --> 00:07:40,060 yendo letra por letra del clave, o dígito a dígito de la clave, 173 00:07:40,060 --> 00:07:45,084 normalmente, su trie termina siendo tipo de ordenados como lo construyes. 174 00:07:45,084 --> 00:07:47,250 En realidad no hace sentido de pensar en la clasificación 175 00:07:47,250 --> 00:07:49,874 de la misma manera en que pensamos acerca con matrices o listas enlazadas, 176 00:07:49,874 --> 00:07:51,070 o tablas hash. 177 00:07:51,070 --> 00:07:54,780 Pero en cierto sentido, su trie está ordenada a medida que avanza. 178 00:07:54,780 --> 00:07:58,630 >> La desventaja, por supuesto, es que un trie se convierte rápidamente en enormes. 179 00:07:58,630 --> 00:08:02,970 Desde todos los puntos de unión, es posible que tener-- si su clave consiste en dígitos, 180 00:08:02,970 --> 00:08:04,880 usted tiene 10 otra lugares a los que pueden ir, que 181 00:08:04,880 --> 00:08:07,490 significa que cada nodo contiene información 182 00:08:07,490 --> 00:08:11,440 acerca de los datos que desea almacenar en ese nodo, más 10 puntos. 183 00:08:11,440 --> 00:08:14,430 Lo cual, en CS50 IDE, es de 80 bytes. 184 00:08:14,430 --> 00:08:17,220 Así que es por lo menos 80 bytes para cada nodo que se crea, 185 00:08:17,220 --> 00:08:19,240 y eso sin contar los datos. 186 00:08:19,240 --> 00:08:24,950 Y si sus nodos son letras en vez de números, 187 00:08:24,950 --> 00:08:27,825 ahora tienes 26 punteros de cada lugar. 188 00:08:27,825 --> 00:08:32,007 Y 26 veces 8 es probablemente 200 bytes, o algo así. 189 00:08:32,007 --> 00:08:33,840 Y usted tiene el capital y usted puede lowercase-- 190 00:08:33,840 --> 00:08:35,381 ver dónde voy con esto, ¿verdad? 191 00:08:35,381 --> 00:08:37,500 Sus nodos pueden conseguir realmente grande, y por lo que el trie 192 00:08:37,500 --> 00:08:40,470 sí, en general, puede conseguir realmente grande, demasiado. 193 00:08:40,470 --> 00:08:42,630 Así que si el espacio es muy alta prima en su sistema, 194 00:08:42,630 --> 00:08:45,830 un trie vez no sea la manera correcta de vaya, a pesar de que sus otros beneficios 195 00:08:45,830 --> 00:08:47,780 ven a jugar. 196 00:08:47,780 --> 00:08:48,710 Soy Doug Lloyd. 197 00:08:48,710 --> 00:08:50,740 Esto es CS50. 198 00:08:50,740 --> 00:08:52,316