Catálogo de obras de estructura de datos de Dahua
Capítulo 1 Introducción a las estructuras de datos 1
1.1 Apertura 2
Si le das a alguien un programa, lo torturarás durante un día entero si le enseñas; Alguien sabe programar y lo torturarás por el resto de su vida.
1.2 ¿Cómo aprendiste la estructura de datos? 3
Después de completar el desarrollo y pasar la prueba, envió el código con orgullo. Después de leer el código, el director del proyecto dio una palmada en la mesa y le dijo: "¿Cómo aprendiste la estructura de datos?"
1.3 Origen de la estructura de datos 4
1.4 Conceptos básicos y terminología 5
p>
Como dice el refrán, "Es difícil para una mujer inteligente preparar una comida sin arroz". trabajo, de lo contrario será un montón de chatarra. Este "medidor" son datos.
1.4.1 Datos 5
1.4.2 Elemento de datos 5
1.4.3 Elemento de datos 6
1.4.4 Objeto de datos 6
1.4.5 Estructura de datos 6
1.5 Estructura lógica y estructura física 7
1.5.1 Estructura lógica 7
1.5. 2 Estructura física 9
1.6 Tipo de datos abstractos 11
Todo el mundo necesita una casa para vivir, pero obviamente no tiene sentido considerar una casa grande si no tienes dinero. Como resultado, han aparecido varios tipos de apartamentos en la vivienda comercial, desde villas con varios cientos de metros cuadrados hasta apartamentos cápsula con sólo dos metros cuadrados...
1.6.1 Tipo de dato 11
.1.6 .2 Tipos de datos abstractos 12
1.7 Revisión resumida 14
1.8 Conclusión 15
El resultado final debe ser que usted les diga a los demás que eres increíble " Estructura de datos, eso es todo.”
Capítulo 2 Algoritmo 17
2.1 Apertura 18
2.2 Relación entre estructura de datos y algoritmo 18
Las personas mayores en la industria informática son un grupo de personas muy talentosas que han hecho que muchos problemas aparentemente irresolubles o difíciles se vuelvan tan maravillosos y mágicos.
2.3 Comparación de dos algoritmos 19
Un día, cuando Gauss estaba en la escuela primaria, el profesor pidió a cada alumno que calculara el resultado de 1+2+...+100. calcula primero, ganará primero...
2.4 Definición del algoritmo 20
Los algoritmos en el mundo real cambian constantemente y ningún algoritmo universal puede resolver todos los problemas. Incluso para un problema pequeño, un algoritmo que sea excelente para resolver este tipo de problemas puede no ser adecuado.
2.5 Características del algoritmo 21
2.5.1 Entrada y salida 21
2.5.2 Finitud 21
2.5.3 Propiedad de determinación 21
2.5.4 Viabilidad 21
2.6 Requisitos para el diseño de algoritmos 22
Encuentre el puntaje promedio del examen de ingreso a la universidad de 100 personas y encuentre el puntaje promedio de todos los candidatos en la provincia Hay una gran diferencia en el tiempo y el almacenamiento de memoria del puntaje promedio. Naturalmente, buscamos algoritmos de alta eficiencia y bajo almacenamiento para resolver el problema.
2.6.1 Corrección 22
2.6.2 Legibilidad 23
2.6.3 Robustez 23
2.6.4 Alta eficiencia de tiempo y baja capacidad de almacenamiento 23
2.7 Método de medición de la eficiencia del algoritmo 24
A medida que el valor de n se hace cada vez mayor, la diferencia en su eficiencia de tiempo se vuelve cada vez más grande. Por ejemplo, algunas personas estudian todos los días, mientras que otras juegan y duermen. Después de graduarse, las primeras están ansiosas por ser contratadas por empresas famosas, mientras que las segundas no tienen dónde encontrar trabajo.
2.7.1 Método estadístico post hoc 24
2.7.2 Método de análisis y estimación ex ante 25
2.8 Crecimiento asintótico de la función 27
2.9 Complejidad del tiempo del algoritmo 29
No es difícil entender la derivación de o grande. Lo que es difícil en realidad son algunas operaciones relacionadas en la secuencia, lo que pone a prueba más conocimientos y habilidades matemáticas.
2.9.1 Definición de complejidad temporal del algoritmo 29
2.9.2 Derivación del método de orden o grande 30
2.9.3 Orden constante 30
2.9.4 Orden lineal 31
2.9.5 Orden logarítmico 32
2.9.6 Orden cuadrático 32
2.10 Complejidad del tiempo común 35
p>A veces, decirte que no pruebes algo también es una especie de transferencia de conocimiento. No es necesario que te muerda una serpiente venenosa para saber que no se debe jugar con las serpientes.
2.11 Peor caso y caso promedio 35
2.12 Complejidad del espacio del algoritmo 36
Cree una matriz con un tamaño de 2050 por adelantado y luego presione todos los años correspondientes al número, si es un año bisiesto, el valor de este elemento de la matriz es 1, si no, es 0. De esta manera, el llamado juicio sobre si un determinado año es bisiesto se convierte en el problema de encontrar el valor de un determinado elemento en esta matriz.
2.13 Resumen y revisión 37
2.14 Conclusión 38
Es admirable que el Viejo Tonto moviera montañas, pero inventar explosivos y excavadoras puede ser más práctico e inteligente .
Capítulo 3 Tabla lineal 41
3.1 Declaración de apertura 42
Los padres afuera de la puerta están apiñados en la puerta y los niños adentro están ordenados, formando una A fuerte contraste. Oye, a veces lo que hacen los adultos es peor que el de los niños.
3.2 Definición de tabla lineal 42
3.3 Tipo de datos abstractos de tabla lineal 45
A veces queremos saber si un determinado niño (como McDull) es en la clase Compañero, la maestra me decía, no, McDull está en Springfield Flower Kindergarten. Esta operación de encontrar si un elemento existe es muy común.
3.4 Estructura de almacenamiento secuencial de mesas lineales 47
Cada vez que terminaba de desayunar, corría a la biblioteca, escogía un buen lugar y guardaba los libros en su bolso. Los libros estaban Colocados uno a uno según los asientos, en una larga fila, nueve asientos estaban ocupados por él.
3.4.1 Definición de almacenamiento secuencial 47
3.4.2 Método de almacenamiento secuencial 47
3.4.3 La diferencia entre la longitud de los datos y la longitud de la tabla lineal 48 p>
3.4.4 Método de cálculo de dirección 49
3.5 Inserción y eliminación de estructura de almacenamiento secuencial 50
Cuando fui a comprar boletos de tren durante el Festival de Primavera, todos estaban haciendo fila Una hermosa mujer se acercó y preguntó: "¿Puedo ir delante de ti?". Esto fue un gran problema. Las personas detrás eran como gusanos y todos tuvieron que dar un paso atrás.
3.5.1 Operación obtener elemento 50
3.5.2 Operación insertar 51
3.5.3 Operación eliminar 52
3.5.4 Ventajas y desventajas de la estructura de almacenamiento secuencial de mesas lineales 54
3.6 Estructura de almacenamiento enlazada de mesas lineales 55
De todos modos, es necesario dejar suficiente espacio entre elementos adyacentes, así que ¿por qué no? todos los elementos? No te preocupes por las ubicaciones vecinas, simplemente ve a donde haya espacio. En cambio, cada elemento sabe dónde está el siguiente elemento.
3.6.1 Solución a la escasez de estructura de almacenamiento secuencial
Método 55
3.6.2 Definición de estructura de almacenamiento lineal vinculada a listas 56
3.6.3 Similitudes y diferencias entre el puntero principal y el nodo principal 58
3.6.4 Descripción del código de la estructura de almacenamiento vinculada a una lista lineal 58
3.7 Lectura de una lista vinculada individualmente 60
3.8 Inserción y eliminación de listas enlazadas individualmente 61
Resultó que el padre sostenía la mano de la madre a la izquierda y la mano del bebé a la derecha mientras caminaba por el camino. De repente, una hermosa mujer caminó hacia ella, el padre la miró aturdido. La madre captó la vista, así que separó al padre y al hijo, tomó la mano izquierda del bebé y caminó hacia adelante rápidamente.
3.8.1 Inserción de lista enlazada individualmente 61
3.8.2 Eliminación de lista enlazada individualmente 64
3.9 Creación de toda la lista enlazada individualmente 66 p>
3.10 Eliminación de toda la tabla de la lista enlazada individualmente 69
3.11 Ventajas y desventajas de la estructura de la lista enlazada individualmente y la estructura de almacenamiento secuencial 70
3.12 Lista enlazada estática 71
Para algunos lenguajes, en los primeros lenguajes de programación de alto nivel, como basic y fortran, dado que no hay punteros, esta estructura de lista vinculada no se puede implementar de acuerdo con nuestra explicación anterior. ¿Qué hacer?
3.12.1 Operación de inserción de lista enlazada estática 73
3.12.2 Operación de eliminación de lista enlazada estática 75
3.12.3 Ventajas y desventajas de la lista enlazada estática lista 77
3.13 Lista circular enlazada 78
Esta idea de la reencarnación es muy interesante. Enfatiza que no importa si eres pobre o rico en esta vida, si continúas haciendo buenas obras y acumulando virtudes, estarás mejor en la próxima vida y viceversa.
3.14 Lista doblemente enlazada 81
Al igual que en la vida de todos, si quieres ganar algo, tienes que pagar un precio. Dado que una lista doblemente enlazada tiene más estructuras de datos que una lista simplemente enlazada, como recorrido inverso y búsqueda, etc., hay que pagar un pequeño precio.
3.15 Repaso resumido 84
3.16 Conclusión 85
Si crees que ir a la escuela es un castigo, suponiendo que puedas vivir hasta los 80 años, en De hecho, sólo vivirás hasta los 80 años. Yo sufrí durante 20 años. Pasar una cuarta parte de tu vida a cambio de una vida feliz el resto de tu vida no es nada.
Capítulo 4 Apilar y hacer cola 87
4.1 Apertura 88
Piénsalo, cuando estás a punto de usar un arma, de repente la pistola claramente tiene balas pero Si no puedes luchar contra ello, ¿no sería fatal?
4.2 Definición de pila 89
Muchos software similares, como Word, Photoshop, etc., tienen operaciones de deshacer, que también se implementan utilizando la pila.
4.2.1 Definición de pila 89
4.2.2 Variaciones de push y pop 90
4.3 Tipos de datos abstractos de pila 91
4.4 La estructura de almacenamiento secuencial y la implementación de la pila 92
4.4.1 La estructura de almacenamiento secuencial de la pila 92
4.4.2 La estructura de almacenamiento secuencial de la operación de inserción de pila 93
4.4.3 Operación pop secuencial de la estructura de almacenamiento de la pila 94
4.5 Dos pilas comparten espacio 94
Dos compañeros de cuarto de la universidad se graduaron y se fueron a trabajar a Beijing en Al mismo tiempo, espero encontrar un apartamento de una habitación o un apartamento de una habitación en el que pueda vivir solo cuando alquile una casa, pero después de buscar, descubro que es realmente inasequible.
4.6 La estructura de almacenamiento en cadena y la implementación de la pila 97
4.6.1 La estructura de almacenamiento en cadena de la pila 97
4.6.2 La estructura de almacenamiento en cadena de la pila Operación Push 98
4.6.3 Estructura de almacenamiento de la cadena de pila Operación Pop 99
4.7 Función de la pila 100
4.8 Aplicación de la pila - recursividad 100
Cuando te paras frente al espejo, hay una imagen tuya en el espejo. ¿Pero alguna vez has intentado mirarte en dos espejos al mismo tiempo? Si dos espejos A y B se colocan uno frente al otro y tú te paras en el medio, hay miles de "encarnaciones" tuyas en ambos espejos.
4.8.1 Implementación de la secuencia de Fibonacci 101
4.8.2 Definición recursiva 103
4.9 Aplicación de la pila: evaluación de cuatro expresiones aritméticas 104
4.9.1 Definición de notación de sufijo (polaco inverso) 104
4.9.2 Resultado del cálculo de expresión de sufijo 106
4.9.3 Conversión de expresión de infijo Expresión de sufijo 108
4.10 Definición de cola 111
La computadora a veces parece estar en estado de falla. Justo cuando pierdes la paciencia y planeas resetear. De repente, fue como despertarse del vino y ejecutar en orden todas las operaciones en las que acababa de hacer clic.
4.11 Tipo de datos abstractos de cola 112
4.12 Cola circular 113
Te subes al autobús y descubres que hay dos asientos vacíos en la primera fila y todos los asientos de la última fila Los asientos ya están llenos, ¿qué harás? Me bajé inmediatamente del auto y me dije, no hay asientos atrás, ¿debería esperar al siguiente? Las personas que no sean tan estúpidas, por supuesto, pueden sentarse allí si hay asientos delante.
4.12.1 Deficiencias del almacenamiento secuencial en cola 112
4.12.2 Definición de cola circular 114
4.13 Estructura e implementación del almacenamiento en cadena de cola 117
4.13.1 Operación de puesta en cola de la estructura de almacenamiento de la cadena de colas 118
4.13.2 Operación de retirada de la cola de la estructura de almacenamiento de la cadena de colas 119
4.14 Resumen y revisión 120
4.15 Conclusión 121
La vida requiere la encarnación del espíritu de cola. Desde la Antártida hasta el Polo Norte, hay solo una cola desde los 90 grados de latitud sur hasta los 90 grados de latitud norte. Si dudas a mitad del camino y haces un giro temporal, es posible que solo puedas quedarte con los pingüinos para siempre. Pero, de hecho, no importa en qué dirección, mientras persistas hasta el final, puedes llegar al final.
Capítulo 5 Chuan 123
5.1 Apertura 124
“Con los ojos secos mirando las montañas lejanas y al otro lado del agua, ¿cuántas veces nos hemos visto? y se conocen? Tengo miedo de que la olla esté vacía y tengo miedo de beber una copa de vino, es difícil escribir poemas armoniosos. El camino está bloqueado y la gente está separada por mucho tiempo, y el mensaje no. Regresó tarde. La lámpara solitaria permanece en silencio durante mucho tiempo, y el marido recuerda a su esposa y a su padre "... Pero después de leerlo detenidamente, descubrí que este poema en realidad se puede leer al revés.
5.2 Definición de cadena 124
Las palabras "sobre", "fin" y "mentira" que mencioné son en realidad las palabras "amante", "amigo" y "creer" Una subcadena de una cuerda.
5.3 Comparación de cadenas 126
5.4 Tipo de datos abstractos de cadenas 127
5.5 Estructura de almacenamiento de cadenas 128
Sucedió emocionalmente Pregunta , para explicárselo a mi novia, iba a enviarle un mensaje de texto y escribí 75 palabras de una vez. Las últimas ocho palabras son "Es imposible que te odie", haz clic en enviar. Más tarde supe que lo que recibió la otra parte fueron solo 70 palabras y el mensaje de texto terminaba con "... te odio".
5.5.1 Estructura de almacenamiento secuencial de cadenas 129
5.5.2 Estructura de almacenamiento encadenado de cadenas 131
5.6 Algoritmo de coincidencia de patrones simple 131
La cadena principal es s="00000000000000000000000000000000000000000000001", y la subcadena que debe coincidir es t="0000000001"... Al hacer coincidir, tengo que recorrer los caracteres en t hasta el último cada vez para descubrirlo, oh , Resulta que no coinciden.
Algoritmo de coincidencia de patrones de 5,7 kmp 135
Hace muchos años, nuestros científicos pensaron que un algoritmo como este que necesita atravesar cadenas con múltiples caracteres repetidos de 0 y 1 uno por uno es muy malo. cosa.
Principio del algoritmo de coincidencia de patrones 5.7.1kmp 135
5.7.2Derivación del valor de la matriz siguiente 139
Implementación del algoritmo de coincidencia de patrones 5.7.3kmp 141
5.7.4kmp mejora del algoritmo de coincidencia de patrones 142
5.7.5derivación del valor de matriz nextval 144
5.8 Revisión resumida 146
5.9 Conclusión 146
"Xuanji Picture" tiene ochocientos cuarenta y cuatro caracteres, con veintinueve caracteres cada uno vertical y horizontalmente. Se pueden formar lecturas vertical, horizontal, oblicua, alternativa, hacia adelante, hacia atrás o hacia atrás por un carácter, o superponiendo un carácter. Un poema. Hay tres tipos de poemas: Puede ser de cuatro, cinco, seis o siete palabras. Según las estadísticas actuales, puede estar compuesto por 7.958 poemas. Escuche con claridad, es la canción 7958.
Capítulo 6 Árbol 149
6.1 Apertura 150
No importa cuán alto o grande sea un árbol, crece de pequeño a grande, de raíces a hojas, poco a poco. Como dice el refrán, se necesitan diez años para cultivar árboles y cien años para cultivar personas, pero se necesitan más de diez años para hacer crecer un árbol grande.
6.2 Definición de árbol 150
La definición de árbol es en realidad el método recursivo que mencionamos al explicar la pila.
Es decir, el concepto de árbol también se utiliza en la definición de árbol. Este es un método de definición relativamente nuevo.
6.2.1 Clasificación de nodos 152
6.2.2 Relación entre nodos 152
6.2.3 Otros conceptos relacionados de árboles 153
6.3 Tipo de datos abstractos del árbol 154
6.4 Estructura de almacenamiento del árbol 155
6.4.1 Representación principal 155
6.4.2 Representación secundaria 158
6.4.3 Representación de los hermanos de los niños 162
6.5 Definición de árbol binario 163
Su Dongpo dijo una vez: "La gente tiene alegrías y tristezas, separación y reencuentro, y la luna Este asunto nunca se ha resuelto en la antigüedad ". Significa que la perfección es el ideal y la imperfección es la vida. Los ejemplos que solemos dar son todos árboles binarios desiguales con alto izquierdo y bajo derecho. Entonces, ¿existe un árbol binario perfecto?
6.5.1 Características de los árboles binarios 164
6.5.2 Árboles binarios especiales 166
6.6 Propiedades de los árboles binarios 169
6.6 .1 Propiedades de los árboles binarios 1 169
6.6.2 Propiedades del árbol binario 2 169
6.6.3 Propiedades del árbol binario 3 169
6.6.4 Árbol binario properties 4 170
6.6.5 Propiedades del árbol binario 5 171
6.7 Estructura de almacenamiento del árbol binario 172
6.7.1 Estructura de almacenamiento secuencial del árbol binario 172
6.7.2 Lista enlazada binaria 173
6.8 Atravesando el árbol binario 174
En el camino de tu vida, enfrentarás opciones como qué ciudad, qué universidad y especialidad específica al completar su solicitud de examen de ingreso a la universidad Debido a los diferentes métodos de selección, el orden de recorrido es completamente diferente.
6.8.1 Principio de recorrido del árbol binario 174
6.8.2 Método de recorrido del árbol binario 175
6.8.3 Algoritmo de recorrido de preorden 178
6.8.4 Algoritmo de recorrido en orden 181
6.8.5 Algoritmo de recorrido en orden posterior 184
6.8.6 Derivación de resultados de recorrido 184
6.9 Construcción del árbol binario 187
6.10 Pista Árbol binario 188
Ahora abogamos por una sociedad orientada a la conservación, y todo debería estar orientado a la conservación. Por supuesto, nuestros programas no son una excepción. Deberíamos considerar ahorrar tiempo o espacio que no se pueda desperdiciar.
6.10.1 Principio del árbol binario de pistas 188
6.10.2 Implementación de la estructura del árbol binario de pistas 191
6.11 Conversión de árboles, bosques y árboles binarios 195
Una empresa del municipio también compró la misma línea de producción. Después de que el patrón descubrió este problema, encontró un trabajador y le dijo: Debes arreglarlo o te despedirán. El trabajador rápidamente encontró una solución: colocó un ventilador al lado de la línea de producción y lo sopló con fuerza para que las cajas de jabón vacías se llevaran naturalmente.
6.11.1 Convertir un árbol en un árbol binario 196
6.11.2 Convertir un bosque en un árbol binario 197
6.11.3 Convertir un árbol binario a un árbol 197
6.11.4 Conversión de árbol binario a bosque 199
6.11.5 Recorrido de árboles y bosques 199
6.12 Árbol de Huffman y su aplicación 200
Compresión ¿Cómo hacerlo sin cometer errores? En pocas palabras, es una tecnología que vuelve a codificar el texto que queremos comprimir para reducir el espacio innecesario. La tecnología de compresión y descompresión se desarrolló basándose en la investigación de Huffman y debemos recordarlo.
6.12.1 Árbol de Huffman 200
6.12.2 Definición y principio del árbol de Huffman 203
6.12.3 Codificación de Huffman 205
p>6.13 Repaso resumido 208
6.14 Conclusión 209
Las personas derraman lágrimas cuando se sienten heridas. Cuando el árbol resulte herido, el cielo nunca más llorará. Espero que nuestro futuro no sólo consista en edificios de gran altura construidos con acero y hormigón, sino que también tengamos frondosos bosques y praderas. Sólo entonces los humanos podremos vivir en armonía con la naturaleza.
Capítulo 7 Figura 211
7.1 Apertura 212
Si no eres bueno planificando, es muy probable que vayas a Hainan después de jugar bien en Xinjiang, y luego correr a Heilongjiang, una decisión tan ridícula.
7.2 Definición de la Figura 213
En realidad, la relación entre las personas es muy complicada. Por ejemplo, mis amigos pueden conocerse. Esto no es simple uno a uno. Relaciones uno a muchos, ese es el tema que vamos a estudiar hoy: los gráficos.
7.2.1 Varias definiciones de gráficos 214
7.2.2 La relación entre los vértices y aristas del gráfico 217
7.2.3 Términos relacionados con gráficos conectados 219
p>
7.2.4 Definición y resumen terminológico del gráfico 222
7.3 Tipo de datos abstractos del gráfico 222
7.4 Estructura de almacenamiento del gráfico 223
Porque la noche en los Estados Unidos es el día en China. Usando Internet, sus empleados pueden monitorear las condiciones reales del almacén estadounidense durante la noche mientras trabajan durante el día. , pueden llamar de inmediato al personal local relevante en los Estados Unidos para que se encargue de ellos. p>
7.4.1 Matriz de adyacencia 224
7.4.2 Lista de adyacencia 228
7.4.3 Lista de enlaces cruzados 232
7.4.4 Lista múltiple de adyacencia 234
7.4.5 Matriz de conjuntos de bordes 236
7.5 Recorrido de gráficos 237
Estaba preparándome para salir una mañana y descubrí que faltaba la llave. Mi hijo debe haber estado jugando con él y lo perdió en algún rincón. ¿Qué crees que debo hacer para encontrarlo?
7.5.1 Recorrido primero en profundidad 238
7.5.2 Recorrido primero en amplitud 242
7.6 Árbol de expansión mínimo 245
Si trabajas horas extras. Además, el resultado que diseñaste día y noche es el plan uno. Creo que no estás lejos de ser despedido (compañero sonríe). Porque el costo de este plan es más de la mitad que los dos últimos planes, lo que hará que el jefe se desmaye de ira.
7.6.1 Algoritmo de Prim 247
7.6.2 Algoritmo de Kruskal 251
7.7 Camino más corto 257
p>
En para ahorrar dinero, algunas personas necesitan la distancia más corta, pero la larga distancia entre las estaciones de transferencia no ahorra tiempo, otras tienen prisa y su mayor necesidad es acortar el tiempo total, y hay otro tipo de personas; No quieren caminar más, la clave es trasladarse menos, para que puedan descansar bien en el coche.
7.7.1 Algoritmo de Dijkstra 259
7.7.3 Algoritmo de Floyd 265
7.8 Clasificación topológica 270
Es imposible hacer una filmar cuando el director no haya sido encontrado cuando el personal se encuentre en el lugar y estacionado en el lugar, ni es posible que el lugar no esté disponible durante el proceso de filmación. Esto puede llevar a resultados absurdos.
7.8.1 Introducción a la clasificación topológica 271
7.8.2 Algoritmo de clasificación topológica 272
7.9 Ruta crítica 277
Si construyes una rueda Se necesitan 0,5 días para fabricar un motor, 3 días para fabricar el chasis de un automóvil, 2 días para fabricar el chasis de un automóvil, 2 días para fabricar una carcasa y 2 días para otras piezas. Se necesitan 0,5 días para reunir todas las piezas. en un solo lugar, y 2 días para armar el auto Disculpe, ¿cuántos días se necesitan para construir un auto en una fábrica de autos?
7.9.1 Principio del algoritmo de ruta crítica 279
7.9.2 Algoritmo de ruta crítica 280
7.10 Revisión resumida 287
7.11 Conclusión 289
La distancia más larga del mundo no es la pequeña brecha entre la vaca A y la vaca C, pero entre ustedes, algunos de ustedes están corriendo hasta el final para ser increíbles, y otros lo aprenden tan pronto cuando entras al campus universitario te rindes.
Capítulo 8 Búsqueda 291
8.1 Declaración inicial 292
Cuando escribes cuidadosamente una publicación de blog o subes un conjunto de fotografías a Internet, personas de todas partes En el mundo pulularán innumerables "arañas". La llamada araña es el software instalado en el servidor de la empresa del motor de búsqueda. Trata Internet como una telaraña y accede a todo tipo de información día y noche.
8.2 Introducción a la Búsqueda 293
Por ejemplo, nuevos términos en la era de Internet, como "vivienda", "tribu de hormigas", etc., si es necesario incluirlos en En el diccionario chino, obviamente deben incluirse cuando se incluyen. Debe averiguar si existen y dónde deben incluirse si no existen.
8.3 Búsqueda en la tabla de secuencias 295
8.3.1 Algoritmo de búsqueda en la tabla de secuencias 296
8.3.2 Optimización de la búsqueda en la tabla de secuencias 297
8.4 Búsqueda de lista ordenada 298
He escrito un número entero positivo dentro de 100 en el papel. Por favor, adivinalo. Puedes adivinarlo después de preguntar varias veces. En ese momento, ya presentamos cómo adivinar este número lo más rápido posible. A este método de buscar el registro del medio cada vez lo llamamos búsqueda binaria.
8.4.1 Búsqueda media 298
8.4.2 Búsqueda por interpolación 301
8.4.3 Búsqueda de Fibonacci 302
8.5 Búsqueda por índice lineal 306
Mi madre es mayor y a menudo no puede encontrar cosas en casa, por lo que usa un pequeño libro para registrar la ubicación de todas las cosas pequeñas en la casa. Por ejemplo, el libro de registro del hogar se coloca debajo del. mesita de noche a la derecha. En el cajón, los billetes están colocados sobre la ropa... Bueno, no voy a mencionar esto.
8.5.1 Índice denso 307
8.5.2 Índice bloqueado 308
8.5.3 Índice invertido 311
8.6 II Clasificación cruzada árbol 313
Luego llegó el tigre, una persona corrió lo más rápido que pudo, mientras el otro se dio cuenta y trepó al árbol. Y los tigres no pueden trepar a los árboles, así que... El escalador de árboles cambió de opinión acerca de correr. Este cambio fue tan importante que le salvó la vida.
8.6.1 Operación de búsqueda del árbol de clasificación binaria 316
8.6.2 Operación de inserción del árbol de clasificación binaria 318
8.6.3 Operación de eliminación del árbol de clasificación binaria 320 p>
8.6.4 Resumen de árboles de clasificación binaria 327
8.7 Árbol binario equilibrado (árbol avl) 328
La tableta es un mundo Cuando llega la tentación, los corazones de las personas si. El equilibrio se rompe, el mundo será caótico y al final todo lo que quedará será soledad y fracaso. Esta sociedad monótona y mecanizada no puede resistir la erosión de la tentación, y quienes son más fácilmente erosionados son precisamente las almas más vacías.
8.7.1 Principio de implementación del árbol binario equilibrado 330
8.7.2 Algoritmo de implementación del árbol binario equilibrado 334
8.8 Árbol de búsqueda de rutas múltiples (árbol b) 341
Para observar si una empresa es rigurosa, basta con mirar cómo celebran sus reuniones. Si durante una reunión todos abren la boca y hablan improvisadamente, definitivamente se trata de una empresa laxa.
8.8.12-3 árbol 343
8.8.22-3-4 árbol 348
8.8.3b árbol 349
8.8 .4b+Tree 351
8.9 Descripción general de la búsqueda en tabla hash (tabla hash) 353
Realmente quieres aprender Tai Chi. Escuché que hay una persona llamada Zhang Sanfeng en la escuela. que es muy bueno en eso, así que fui a la oficina de estudiantes de la escuela para buscar a alguien. El personal sacó la lista de estudiantes y finalmente les dijo que no existía tal persona en la escuela y que Zhang Sanfeng había muerto en la montaña Wudang. de años atrás.
8.9.1 Definición de búsqueda en tabla hash 354
8.9.2 Pasos de la búsqueda en tabla hash 355
8.10 Método de construcción de la función hash 356
8.10.1 Método de direccionamiento directo 357
8.10.2 Método de análisis digital 358
8.10.3 Método de centrado en escuadra 359
8.10.4 Método de plegado 359
8.10.5 Método de división con resto 359
8.10.6 Método de números aleatorios 360
8.11 Método para tratar conflictos hash 360
Cada uno de nosotros quiere estar sano. Aunque las enfermedades se pueden prevenir, son inevitables. Nadie puede decir que no ha estado enfermo una vez desde que nació.
8.11.1 Método de direccionamiento abierto 361
8.11.2 Método de función de refrito 363
8.11.3 Método de dirección en cadena 363
8.11 .4 Método de área de desbordamiento de *** público 364
8.12 Implementación de búsqueda de tabla hash 365
8.12.1 Implementación del algoritmo de búsqueda de tabla hash 365
8.12. análisis de rendimiento de búsqueda de tablas 367
8.13 Revisión resumida 368
8.14 Conclusión 369
Si soy una persona a la que le gustan los automóviles, a menudo busco información sobre ellos. Entonces, cuando ingreso palabras clave como "Escarabajo" y "Jaguar" en el cuadro de búsqueda, no permita que animales y personas se conviertan en los titulares de la búsqueda.
Capítulo 9 Clasificación 373
9.1 Apertura 374
Supongamos que quiero comprar un iPhone 4, así que voy a un sitio web de comercio electrónico para buscar. Después de buscar, encontré que hay 8863 artículos relacionados. Hay tantos que me resulta difícil elegir. De hecho, quiero comprar algo más barato, pero tengo miedo de encontrarme con estafadores y quiero encontrar un comerciante de confianza. ¿Qué debo hacer?
9.2 Conceptos básicos y clasificaciones del ranking 375
Por ejemplo, para seleccionar a los estudiantes que son mejores en las materias principales, algunas de nuestras universidades requieren que todos los estudiantes se clasifiquen en orden inverso. por sus puntuaciones totales en todas las materias y en el caso de la misma puntuación total, las puntuaciones totales distintas de lengua y matemáticas se clasifican en orden inverso. Esta es la clasificación combinada de las dos subpalabras clave, la puntuación total y la puntuación total distinta del número de palabras.
9.2.1 Estabilidad de la clasificación 376
9.2.2 Clasificación interna y clasificación externa 377
9.2.3 Estructuras y funciones utilizadas en la clasificación 378
9.3 Clasificación por burbujas 378
No importa qué lenguaje de programación aprenda, cuando aprenda bucles y matrices, generalmente se le presentará un algoritmo de clasificación, y este algoritmo suele ser de clasificación por burbujas. No es que su nombre sea bonito, sino que la idea de este algoritmo es la más sencilla y fácil de entender.
9.3.1 La implementación de clasificación más simple 379
9.3.2 Algoritmo de clasificación de burbujas 380
9.3.3 Optimización de clasificación de burbujas 382
9.3.4 Análisis de complejidad de clasificación de burbujas 383
9.4 Clasificación de selección simple 384
También hay un tipo de personas que hacen acciones y rara vez actúan y simplemente siguen observando y juzgando. esperar la oportunidad para comprar o vender con decisión. Debido a que están tranquilos y serenos, y a que comercian con menos frecuencia, terminan ganando mucho dinero.
9.4.1 Algoritmo de clasificación por selección simple 384
9.4.2 Análisis de complejidad de clasificación por selección simple 385
9.5 Clasificación por inserción directa 386
Incluso si es la primera vez que juegas al póquer, siempre que conozcas estos números, no es necesario que te enseñen a manejar las cartas. Mueva 3 y 4 a la izquierda de 5, y luego mueva 2 hacia el extremo izquierdo y se ordenará el orden. Aquí, nuestro método de gestión de tarjetas es el método de clasificación por inserción directa.
9.5.1 Algoritmo de clasificación por inserción directa 386
9.5.2 Análisis de complejidad de clasificación por inserción directa 388
9.6 Clasificación Hill 389
En En cualquier caso, la invención del algoritmo de clasificación de Hill nos permitió finalmente superar la era de la clasificación lenta (más allá de la complejidad temporal de o (n2)). Después de eso, aparecieron algoritmos de clasificación más eficientes uno tras otro.
9.6.1 Principio de clasificación Hill 391
9.6.2 Algoritmo de clasificación Hill 391
9.6.3 Análisis de complejidad de clasificación Hill 395
9.7 Clasificación de montón 396
¿Qué es una estructura de montón? Recordemos que cuando éramos jóvenes, especialmente los compañeros varones, básicamente hacíamos la broma de apilar Arhats. Por lo general, la persona que quiere ser castigada es empujada al suelo primero, y luego todos se agolpan y se abalanzan sobre él... ¿Las consecuencias? La consecuencia, por supuesto, es reírse de ello.
9.7.1 Algoritmo de clasificación de montón 398
9.7.2 Análisis de complejidad de clasificación de montón 405
9.8 Clasificación por combinación 406
Incluso si Eres el primero de tu clase, o incluso el primero de tu grado. Si no alcanzas el puntaje, significa que tu puntaje no se encuentra entre los 10,000 mejores de la provincia y básicamente has perdido la oportunidad de estudiar. para obtener una licenciatura ese año.
9.8.1 Algoritmo de ordenación por combinación 407
9.8.2 Análisis de complejidad de ordenación por combinación 413
9.8.3 Implementación no recursiva de ordenación por combinación 413
9.9 Clasificación rápida 417
Finalmente nuestro maestro está a punto de aparecer. En el futuro, después de que trabajes, tu jefe te pedirá que escribas un algoritmo de clasificación, pero el algoritmo que conoces no lo incluye. clasificación rápida. Creo que será mejor que te quedes callado y busques en secreto el algoritmo de clasificación rápida y lo escribas en la computadora, así al menos no todos se reirán de ti.
9.9.1 Algoritmo de clasificación rápida 417
9.9.2 Análisis de complejidad de clasificación rápida 421
9.9.3 Optimización de clasificación rápida 422
9.10 Revisión resumida 428
Actualmente no existe un algoritmo de clasificación perfecto. Tiene ventajas y desventajas. Incluso el método de clasificación rápida solo es superior en rendimiento general. También tiene una clasificación inestable y requiere una gran cantidad de datos. Existen deficiencias como el espacio auxiliar y ninguna ventaja a la hora de ordenar una pequeña cantidad de datos.
9.11 Epílogo 430
Si tienes un sueño, defiéndelo. Cuando otros no pueden hacerlo, quieren decirte que tú tampoco puedes. Si quieres algo, tienes que trabajar duro para conseguirlo. ¡eso es todo!
Referencias del Apéndice 435