Consulta de código fuente de índice multidimensional
Resumen de la revisión de la estructura de datos [Adecuado para el libro de texto de la edición Tsinghua Yan Weimin]
Estructura del capítulo y componentes clave de la estructura de datos
Los capítulos de la materia de estructura de datos se dividen básicamente en: introducción, tablas lineales, pilas y colas, cadenas, arreglos multidimensionales y tablas generalizadas, árboles y árboles binarios, gráficos, búsqueda, filas internas, filas externas, archivos y asignación de almacenamiento dinámico.
Para la mayoría de las escuelas, los tres capítulos de "Salida, archivos y asignación dinámica de almacenamiento" básicamente no se prueban y básicamente no se enseñan en el proceso de enseñanza de pregrado en informática en la mayoría de las universidades. Por lo tanto, no es necesario que gastes demasiada energía en estos tres capítulos, siempre que conozcas los conceptos básicos. Pero para aquellos que postulan a escuelas prestigiosas, especialmente escuelas, y tienen un historial de evaluar estos tres capítulos en el examen, entonces estos amigos deberían prestar atención a estos tres capítulos.
Según los capítulos anteriores y la introducción de los siguientes tres capítulos, la proporción de capítulos en la estructura de datos es aproximadamente la siguiente:
Introducción: muy poco contenido, conceptos simples , la mayoría La puntuación es de solo unos pocos puntos y algunas escuelas ni siquiera realizan el examen.
Tabla lineal: capítulo básico, uno de los contenidos obligatorios. La mayoría de las preguntas del examen son preguntas de conceptos básicos y hay muy pocas preguntas de diseño de algoritmos a gran escala de escuelas prestigiosas. Si es así, también se combina con otros capítulos.
Apilar y hacer cola: capítulo básico, preguntas de conceptos básicos fáciles de dar, uno de los exámenes imprescindibles. La pila a menudo se examina junto con otros capítulos y, a menudo, se asocia con conceptos como la recursividad.
Cadenas: Capítulo básico, el concepto es relativamente simple. Hay pocas cuestiones de diseño de algoritmos a gran escala dedicadas a este capítulo, y es más común analizar algoritmos en términos de KMP.
Matrices multidimensionales y tablas generalizadas
En el capítulo básico, las preguntas sobre algoritmos basados en matrices también son relativamente comunes y la relación de puntuación fluctúa mucho, por lo que es la "unidad opcional" o "unidad de espera" de la pregunta". En términos generales, si hay preguntas que hacer, la mayoría de ellas no serán preguntas importantes. Las matrices a menudo se combinan con capítulos como "Búsqueda y clasificación" como tema principal.
Árbol y Árbol Binario
: Capítulos claves y difíciles, requeridos por todas las escuelas. La diferencia entre las escuelas en este capítulo es si este capítulo presenta uno o dos grandes problemas de diseño de algoritmos. A través del análisis de los exámenes de muchas escuelas, la mayoría de las escuelas tienen un historial de preguntas de diseño de algoritmos a gran escala en este capítulo.
Imagen: Capítulos claves y difíciles, especialmente escuelas famosas. Si la atención se centra en los exámenes, a menudo aparecen en preguntas de análisis y diseño, y se pueden utilizar junto con tres capítulos para formar un diseño de preguntas para preguntas de diseño de algoritmos.
Buscando
Capítulos claves y difíciles, con muchos conceptos, conexiones estrechas y fácil confusión. Las preguntas pueden formularse como preguntas analíticas y también son comunes en preguntas de conceptos básicos. Las preguntas de diseño de algoritmos se pueden probar mediante combinaciones de matrices o combinarse con capítulos de árbol.
Clasificación
Al igual que el capítulo de búsqueda, este capítulo es clave y difícil con más conceptos, conexiones más estrechas y confusión más fácil. Al examinar los conceptos básicos, me gusta especialmente comparar las ventajas y desventajas de varios algoritmos de clasificación. En el gran problema del diseño de algoritmos, si es un problema, a menudo se examina en combinación con matrices.
En segundo lugar, describe los puntos clave de cada capítulo de la estructura de datos:
Descripción general del Capítulo 0
Este capítulo sirve principalmente como una guía para que los lectores aprendan. datos. Sentar algunas bases para la estructura. Nos centramos principalmente en los siguientes puntos: los conceptos básicos de las estructuras de datos, los conceptos y métodos de medición de la complejidad del tiempo y el espacio, y consideraciones para el diseño de algoritmos. No hay muchos puntos de prueba en este capítulo, solo preste atención a la comprensión.
Capítulo 1 Tablas lineales
Como capítulo inicial de estructuras lineales, el capítulo de tablas lineales juega un papel importante en el estudio de estructuras lineales e incluso en toda la disciplina de estructuras de datos. Este capítulo presenta sistemáticamente el concepto de almacenamiento en cadena por primera vez. No importa qué capítulo involucre este concepto, el almacenamiento en cadena será la parte más importante de toda la disciplina de estructura de datos.
En términos generales, los puntos de prueba importantes en este capítulo de tablas lineales se pueden examinar desde los siguientes aspectos:
1. Conceptos básicos relacionados con las tablas lineales, como predecesor, sucesión, Longitud de la tabla, tabla vacía, nodo principal, nodo principal, puntero principal, etc.
2. Las características estructurales de las tablas lineales significan principalmente que cada nodo tiene solo un predecesor y un sucesor además del primer y último elemento.
3. El método de almacenamiento secuencial de tablas lineales y sus dos implementaciones diferentes en entornos de lenguaje específicos: asignación estática y asignación dinámica de espacio de tabla. Similitudes y diferencias entre listas enlazadas estáticas y listas enlazadas secuenciales.
4. El método de almacenamiento vinculado de listas lineales y las características y operaciones de las siguientes listas vinculadas de uso común: listas vinculadas individualmente, listas vinculadas circulares, listas doblemente vinculadas y listas vinculadas circulares bidireccionales. Entre ellos, el algoritmo de fusión de listas enlazadas individualmente, el algoritmo de fusión de listas enlazadas circulares, los algoritmos de inserción y eliminación de listas enlazadas doblemente y listas enlazadas doblemente circulares son métodos de verificación comunes. Además, en los últimos años, muchas escuelas han encontrado problemas que requieren algoritmos recursivos para implementar una salida de lista enlazada individualmente (ya sea en orden o en orden inverso).
En la pregunta sobre listas enlazadas, a menudo recibimos algunas preguntas como: juzgar una lista vacía. En diferentes listas vinculadas, la forma de determinar la lista vacía es diferente. Tenga en cuenta.
5. En el caso del almacenamiento secuencial de mesa lineal y el almacenamiento en cadena, se comparan sus diferentes ventajas y desventajas, es decir, sus respectivas ocasiones de aplicación. Las ventajas de configurar el puntero principal en una lista enlazada individualmente y el puntero final en una lista enlazada circular sin configurar el puntero principal y la estructura de almacenamiento del índice.
Capítulo 2 Pilas y colas
Las pilas y colas son los primeros obstáculos que encuentran muchos estudiantes que aprenden DS. Muchas personas comenzaron a marearse a partir de este capítulo y han continuado teniendo mareos hasta ahora. Por lo tanto, comprender las pilas y las colas es la única forma de dominar DS.
Antes de estudiar este capítulo, puede preguntarse si ya conoce los siguientes puntos:
1. Las definiciones de pilas y colas y conceptos relacionados de estructuras de datos, que incluyen: pila secuencial. , Pila en cadena, * * * * pila compartida, cola circular, cola en cadena, etc. Características del acceso a la pila y la cola a los datos (tenga en cuenta que incluye partes de almacenamiento y recuperación).
2. Algoritmo recursivo. La relación entre pila y recursividad, el algoritmo clásico que convierte la recursión en no recursiva con la ayuda de pila: ¡n! Problema factorial, problema de secuencia fib, problema de Hanoi, problema de mochila, problemas de recorrido recursivo y no recursivo de árboles binarios, la relación entre el recorrido de profundidad del gráfico y la pila, etc. La mayoría de las cuestiones relacionadas con árboles y gráficos se examinan en los capítulos pertinentes sobre árboles y gráficos.
3. Aplicación de la pila: el principio de resolución de expresiones numéricas y la coincidencia de paréntesis son solo una comprensión teórica. No hay muchos requisitos específicos para examinar el diseño del algoritmo de esta pregunta.
4. Condiciones para determinar si la cola está vacía o llena en una cola circular, y algoritmos para hacer cola y quitarla de la cola en una cola circular.
Si está familiarizado con los puntos anteriores, puede omitir el capítulo sobre pila y cola. Tenga en cuenta que dije que puede dejar de leer, no que puede dejar de escribir preguntas.
Capítulo 3: Xian
Después de experimentar el doloroso sufrimiento del capítulo de la pila, finalmente llegó el capítulo de la serie.
Las cadenas son conceptualmente un capítulo relativamente pequeño y uno de los más fáciles de estudiar por su cuenta, pero cualquiera que lo haya experimentado sabe que el algoritmo KMP es un paso importante en este capítulo. Después de pasar este paso, hay otro gran río de montaña DS en Mapingchuan, jaja.
La serie de capítulos que necesitan romper la fortaleza principal son:
1. El concepto básico de cadenas, la relación entre cadenas y tablas lineales (las cadenas son una tabla lineal especial, Sus elementos son todos datos de caracteres), la diferencia entre cadenas vacías y cadenas en blanco, y las condiciones para la igualdad de cadenas.
2. Operaciones básicas sobre cadenas y el uso de estas funciones básicas, incluidas subcadenas, concatenación de cadenas, reemplazo de cadenas, cálculo de longitud de cadenas, etc. El uso de operaciones básicas en cadenas para completar un algoritmo específico es el enfoque de muchas escuelas en operaciones básicas.
3. Las diferencias y conexiones entre cadenas de secuencia, cadenas de cadena y cadenas de blockchain, así como los métodos de implementación.
4. La idea del algoritmo KMP. Solución para KMP next array y nextval array. Identificar las deficiencias de los algoritmos tradicionales de coincidencia de patrones y las áreas de mejora. Entre ellos, el algoritmo de comprensión es el núcleo y la matriz es el punto de puntuación. No hace falta decir que esta sección es la más importante del capítulo. Una posible forma de comprobarlo es encontrar los valores de matriz de next y nextval, y realizar el proceso de coincidencia utilizando el algoritmo KMP en función del valor de matriz obtenido de next o nextval.
Capítulo 4 Arreglos y Tablas Generalizadas
Para aquellos que han aprendido lenguajes de programación, esta no es la primera vez que ven el concepto de arreglos. Debe "nacer una vez, cocinarse". dos veces", por lo que no habrá mucho obstáculo conceptual. Sin embargo, como curso de posgrado, el enfoque de este capítulo puede ser diferente del lenguaje de programación de la universidad, que se presentará a continuación.
El concepto de tablas generalizadas apareció por primera vez en las estructuras de datos. Es una lista lineal o una secuencia finita de elementos de la tabla. Cada sublista o elemento que compone la estructura también es lineal, por lo que este capítulo también se clasifica como una estructura lineal.
El enfoque de este capítulo es:
1. Resolver la posición de los elementos de una matriz en matrices multidimensionales. Generalmente, se dan la dirección del primer elemento de un elemento de matriz y el espacio de direcciones ocupado por cada elemento. Se dan las dimensiones de una matriz multidimensional y luego se le pide que encuentre la posición de un elemento en la matriz.
2. Aclare las diferencias y conexiones entre el almacenamiento en filas y el almacenamiento en columnas, y sea capaz de resolver el problema en 1 en función de estos dos métodos de almacenamiento diferentes.
3. Almacene los elementos de la matriz especial en la matriz de acuerdo con el método de conversión correspondiente. Estas matrices incluyen: matrices simétricas, matrices triangulares, matrices dispersas con determinadas características, etc. Familiarícese con las tres formas diferentes de almacenar matrices dispersas: triplete, binario con vectores de fila auxiliares y almacenamiento de listas entrecruzadas. Domine el algoritmo para convertir triples o 2 tuplas de matrices dispersas en listas entrecruzadas.
4. El concepto de tablas generalizadas, especialmente las definiciones de encabezados y colas de tablas. Ésta es la base para comprender el algoritmo de sección completa de tabla generalizada. Recientemente, ha aparecido un tipo de pregunta de este tipo en algunas escuelas: después de realizar varias operaciones de cabeza y cola en una determinada tabla generalizada L, se proporciona un valor de cadena y se encuentra la tabla generalizada L original.
5. Algoritmos recursivos relacionados con tablas generalizadas. Debido a que la definición de tablas generalizadas es recursiva, los algoritmos asociados con tablas generalizadas suelen ser recursivos. Por ejemplo: encontrar la profundidad de una tabla, copiar una tabla generalizada, etc. Este problema se puede resolver de dos maneras diferentes desde diferentes perspectivas según la forma de expresión de la tabla generalizada: una es tratar la tabla generalizada como el principio y el final de la tabla, y operar el principio y el final de la tabla respectivamente; el segundo es utilizar una La tabla generalizada se considera como varias subtablas y cada subtabla se opera por separado.
Capítulo 5 Árboles y árboles binarios
Del aprendizaje excesivo de estructuras lineales al aprendizaje de estructuras de árbol es un salto en los cursos de estudio de estructuras de datos. La realización de este salto afectará directamente si puede lograr puntajes altos en el examen real y, en última instancia, todo esto afectará su puntaje total en los cursos profesionales. Por tanto, la importancia de este capítulo para los árboles es evidente.
En términos generales, los puntos de conocimiento en el capítulo del árbol incluyen:
El concepto, las propiedades y la estructura de almacenamiento de los árboles binarios, tres algoritmos para el recorrido del árbol binario (recursivo y no recursivo) , Basado en tres Otros algoritmos de algoritmos transversales básicos, el concepto de árboles binarios de pistas, algoritmos de pistas y algoritmos de búsqueda post-cue, el concepto, composición y aplicación de árboles binarios óptimos, el concepto y la forma de almacenamiento de árboles, recorrido de árboles y bosques. algoritmos y su relación con algoritmos de recorrido de árboles binarios Conversión de relaciones, árboles y bosques a árboles binarios.
Echemos un vistazo a los principales métodos de prueba de los conocimientos anteriores en el examen:
1. El concepto, las propiedades y la estructura de almacenamiento de los árboles binarios.
Los métodos de prueba pueden ser: examinar directamente la definición de un árbol binario para poder explicar la diferencia entre un árbol binario y un árbol binario ordinario; examinar las propiedades de un árbol binario completo y un árbol binario completo, y las cinco propiedades de; un árbol binario común: el número máximo de nodos en el primer nivel, el número máximo de árboles binarios con una profundidad de k El número de nodos, la propiedad de n0=n2+1, la profundidad del árbol binario completo de n nodos , La relación de conversión entre los nodos secundarios y los nodos principales cuando el árbol binario se almacena secuencialmente (izquierda: 2 * i, derecha: 2 * I+65438+)
Las ventajas y desventajas del almacenamiento secuencial del árbol binario y Almacenamiento de listas enlazadas binarias y sus ocasiones aplicables, el método de representación del árbol binario y la lista enlazada triple.
2. Tres algoritmos transversales para árboles binarios.
El dominio de este punto de conocimiento afectará directamente si se puede comprender el algoritmo en el capítulo del árbol y luego afectará si el problema de diseño del algoritmo en el capítulo del árbol se puede completar con éxito. Hay tres algoritmos transversales para árboles binarios: preorden, inorden y postorden. La base para su división depende de la secuencia de acceso a los datos del nodo raíz en cada algoritmo. Es necesario no solo dominar los tres algoritmos recursivos de recorrido y comprender los pasos reales de su implementación, sino también dominar los tres algoritmos de recorrido no recursivos. Debido a que muchos de los algoritmos de este capítulo sobre árboles binarios se pueden convertir directamente a partir de tres algoritmos recursivos (como encontrar el número de hojas), después de dominar los tres algoritmos no recursivos para el recorrido, podemos ocuparnos de "Usar métodos no recursivos". algoritmos para encontrar el número de hojas en un árbol binario" "Este tipo de tema es como un dios. En otra serie de artículos (), daré versiones memorizadas de tres algoritmos transversales recursivos y no recursivos, así que recuérdelos con atención.
3. Otros algoritmos de árbol binario que se pueden mejorar sobre la base de los tres algoritmos transversales:
Encuentre el número de hojas, el número total de nodos del árbol binario y el número total. de nodos con grado 1 o grado 2, copiar el árbol binario, construir un árbol binario, intercambiar los subárboles izquierdo y derecho, encontrar el nodo especificado con valor n, eliminar el nodo especificado con valor n, etc.
Si puede dominar los algoritmos transversales recursivos y no recursivos de los árboles binarios, resolver los problemas anteriores será pan comido.
4. Árbol binario de pistas:
El árbol binario de pistas se introduce para evitar soluciones recursivas durante el recorrido del árbol binario. Como todos sabemos, la recursividad es fácil de entender en su forma, pero consume muchos recursos de memoria. Si hay demasiados niveles de recursividad, inevitablemente habrá un riesgo de agotamiento de los recursos. Para evitar esta situación, el árbol binario de pistas aparece públicamente. Para los árboles binarios de pistas, debe dominar: la naturaleza de las pistas, los algoritmos de tres pistas, el algoritmo transversal de los árboles binarios de pistas y otros problemas algorítmicos de los árboles binarios de pistas básicos (como encontrar el nodo predecesor o sucesor de un nodo específico en cierto tipo de árbol binario de pistas es un problema común).
5. Árbol binario óptimo (árbol de Huffman):
El árbol binario óptimo es una estructura de árbol binario especial que se utiliza para resolver problemas específicos. Su premisa es asignar un peso a cada lado del árbol binario para que la suma de los pesos del árbol binario sea mínima. En la sección del árbol binario óptimo, hay pocas pruebas directas del código fuente del algoritmo. Generalmente, se le proporciona un conjunto de datos y se le pide que construya un árbol binario óptimo basado en este conjunto de datos y encuentre la suma de sus pesos mínimos. Este tipo de preguntas no es muy difícil y es un subtema.
6. Árboles y bosques:
El árbol binario es un tipo especial de árbol. Es especial no solo porque tiene como máximo 2 ramas, ¡sino también por su orden! En otras palabras, los subárboles izquierdo y derecho de un árbol binario no se pueden intercambiar. Si los intercambias, se convertirá en otro árbol binario. De esta forma, pensamos que el árbol binario intercambiado es diferente del árbol binario original. Sin embargo, para los árboles ordinarios de dos ramas, no tiene esta propiedad.
El recorrido de árboles y bosques no es tan rico como el de los árboles binarios. Tienen solo dos algoritmos de recorrido: raíz anterior y raíz posterior (llamado recorrido del bosque en orden previo y posterior). En el examen más difícil, también hay dos algoritmos que requieren que diseñes otros algoritmos basados en estos dos algoritmos. Generalmente, los colegios y universidades rara vez tienen este método. Como máximo, solo requieren que escribas su secuencia transversal de acuerdo con la primera o segunda raíz. El recorrido de la primera y segunda raíz en un árbol binario tiene una relación correspondiente con el algoritmo de recorrido: el primer recorrido corresponde al recorrido de primer orden del árbol binario y el segundo recorrido corresponde al recorrido de orden intermedio del árbol binario. árbol. Este se ha convertido en un centro de exámenes para muchas escuelas, con una variedad de métodos de examen. Algunos prueban esta oración directamente, mientras que otros le piden que primero resuelva la secuencia transversal y luego responda esta pregunta. Los árboles binarios, los árboles y los bosques pueden tener la relación correspondiente anterior, gracias a la lista binaria enlazada. Un árbol binario usa una lista binaria enlazada para almacenar sus hijos izquierdo y derecho, el árbol usa una lista binaria enlazada para almacenar a sus hijos y hermanos (llamada lista enlazada de hermanos del niño), y el bosque también usa una lista binaria enlazada para almacenar sus hijos y hermanos.
Shu Zhang, en todas partes está la clave, el camino es la pregunta del examen, todos deben pasar el examen.
Imagen del Capítulo 6
Si la transformación de la estructura lineal a la estructura de árbol es una sublimación de la investigación sobre la forma de organización de datos en la disciplina de estructura de datos, entonces de la investigación sobre la estructura de árbol a La transformación de la investigación sobre estructuras gráficas ilustra aún más el importante papel de las estructuras de datos en la resolución de problemas prácticos.
Las características de este capítulo son: muchos conceptos, estrechamente relacionados con el concepto de gráficos en matemáticas discretas, algoritmos complejos, fáciles de probar y propensos a grandes preguntas, especialmente en escuelas prestigiosas. Como curso de posgrado, es casi impensable sin examinar el conocimiento de los capítulos de árboles y gráficos.
Echemos un vistazo a los principales puntos de prueba de este capítulo y los métodos de examen para estos puntos de prueba:
1. Verifique los conceptos básicos de gráficos:
Estos conceptos son para aprender gráficos Capítulo 1: Conceptos básicos. Los conceptos de este capítulo incluyen: definición y características de gráficos, gráficos no dirigidos, gráficos dirigidos, gráficos de entrada y de grado, gráficos completos, subgrafos generados, longitudes de camino, ciclos, gráficos (fuertemente) conectados, componentes (fuertemente) conectados, etc. . También se dominan los problemas computacionales relacionados asociados con estos conceptos.
2. Compruebe varias formas de almacenamiento de gráficos:
Las formas de almacenamiento de gráficos incluyen matriz de adyacencia, lista de adyacencia (inversa), lista entrecruzada y lista múltiple de adyacencia. Durante el examen, algunas escuelas proporcionan un formulario de almacenamiento y requieren que los candidatos utilicen algoritmos o escriban manualmente otro formulario de almacenamiento del gráfico correspondiente a la estructura dada.
3. Examine dos algoritmos de recorrido de gráficos: recorrido en profundidad y recorrido en ancho.
El recorrido en profundidad y el recorrido en amplitud son dos algoritmos de recorrido básicos para gráficos. La importancia de estos dos algoritmos para el capítulo del gráfico es equivalente a la importancia del "recorrido en orden previo, en orden y posterior" para el capítulo. de la importancia del árbol binario.
Durante el examen, las preguntas de diseño de algoritmos en el Capítulo 1 de la Figura a menudo se diseñan en función de estos dos algoritmos transversales básicos, como "encontrar el problema de encontrar el camino más largo y el más corto" y "determinar si existe un camino simple de longitud k entre dos vértices". "Problema", utilizando algoritmos de recorrido de amplitud y recorrido de profundidad respectivamente.
4. Los conceptos de árbol de expansión y árbol de expansión mínimo y la construcción del árbol de expansión mínimo: algoritmo PRIM y algoritmo KRUSKAL.
Durante el examen, generalmente no es necesario escribir el código fuente del algoritmo. En cambio, basándose en las ideas del algoritmo de estos dos árboles de expansión mínima, escriba el proceso de construcción y el árbol de expansión mínima generado final.
5. Problema de clasificación topológica:
Hay dos métodos de clasificación topológica, uno es el algoritmo de primer vértice sin predecesores y el otro es el algoritmo de primer vértice sin sucesores. En otras palabras, uno clasifica de adelante hacia atrás y el otro clasifica de atrás hacia adelante. Por supuesto, el resultado de esta última clasificación es el "orden topológico inverso"
6. Problema de ruta crítica:
Este problema es un problema difícil en el primer capítulo del gráfico. Hay tres claves para comprender la ruta crítica: primero, cuál es la ruta crítica; segundo, cuál es el primer momento y cómo obtenerlo; tercero, cuál es el último momento y cómo obtenerlo; En pocas palabras, la hora más temprana se encuentra usando el método "de adelante hacia atrás", mientras que la hora más reciente se encuentra usando el método "de atrás hacia adelante", y la hora más reciente se encuentra solo después de que se hayan encontrado todas las horas más tempranas. . Esta pregunta no pretende probar directamente el código fuente del algoritmo. Generalmente es necesario describir el proceso y los pasos de la solución de acuerdo con el algoritmo del libro.
Al diseñar el algoritmo de ruta crítica, también debemos prestar atención a los siguientes puntos: utilizando la estructura de almacenamiento de la lista de adyacencia, se deben utilizar diferentes métodos de procesamiento para encontrar el momento más temprano y el más reciente, es decir, es, al comienzo del algoritmo, primero establezca los tiempos más tempranos de todos los vértices en 0. El problema de la ruta crítica es un método importante para el control del progreso del proyecto y tiene una gran practicidad.
7. Problema del camino más corto:
Junto con el problema del camino crítico, se denominan dos obstáculos en la Figura 1. Los conceptos son fáciles de entender, la clave es entender el algoritmo. Hay dos tipos de problemas de camino más corto: uno es encontrar el camino más corto desde un determinado punto a otros puntos; el segundo es encontrar el camino más corto entre cada par de vértices en el gráfico. Este problema también tiene características de fondo muy realistas. Una de ellas debería ser la selección de atracciones turísticas y rutas de viaje. El primer problema se resuelve utilizando el algoritmo DIJSKTRA y el segundo problema se resuelve utilizando el algoritmo FLOYD. Note la diferencia.
Capítulo 7 Búsqueda
En muchos libros de texto sobre estructuras de datos, la búsqueda y la clasificación se ubican en estructuras de datos avanzadas. Cabe decir que los dos capítulos de búsqueda y clasificación son una aplicación integral del conocimiento que hemos aprendido antes, utilizando conocimientos como árboles y listas vinculadas, y un aspecto de la aplicación de estas estructuras de datos constituye la búsqueda y clasificación.
En la vida real, la búsqueda está en casi todas partes, especialmente en la era actual de Internet. Todo es inseparable de la búsqueda, desde la búsqueda de caracteres en documentos hasta la búsqueda en Internet, la búsqueda ocupa la mayor parte de nuestro tiempo en línea.
Al revisar el conocimiento de este capítulo, primero debe comprender los siguientes conceptos:
El significado de las palabras clave, las palabras clave primarias y las palabras clave secundarias; el significado y la diferencia entre la búsqueda estática y la búsqueda estática; búsqueda dinámica; promedio Debe recordarse el concepto de longitud de búsqueda ASL y sus métodos de cálculo y resultados en varios algoritmos de búsqueda, especialmente los valores de ASL de algunas estructuras típicas.
En los libros de texto de DS, las búsquedas generalmente se dividen en tres categorías: primero, buscar en la lista de secuencias; 2. buscar en la tabla de árbol; 3. verificar la tabla hash; A continuación se presentan en detalle los puntos de conocimiento y los métodos del examen:
1. Buscar en una tabla lineal:
Se divide principalmente en tres tipos: tabla de secuencia, tabla de secuencia ordenada, y tabla de secuencia de índice. Para el primero, utilizamos métodos de búsqueda tradicionales y los comparamos uno por uno. Usamos el método de búsqueda binaria para ordenar la lista ordenada. Para la tercera estructura de índice, utilizamos un algoritmo de búsqueda de índice. Los candidatos deben prestar atención a los valores de ASL en estas tres tablas y a la implementación de los tres algoritmos. Entre ellos, el método de búsqueda binaria debe prestar especial atención a sus condiciones aplicables y su método de implementación recursivo.
2. Buscar en la tabla del árbol:
Este es el enfoque y la dificultad de este capítulo. Debido a que esta sección presenta la búsqueda utilizando tablas de árbol, es fácil confundirse con algunos conceptos del árbol uno. El contenido de esta sección está relacionado con el contenido del capítulo del árbol, pero existen muchas diferencias que deben tenerse en cuenta. Las tablas de árbol se dividen principalmente en las siguientes categorías: árboles de clasificación binaria, árboles binarios equilibrados, árboles B y árboles clave.
Entre ellos, especialmente las dos primeras estructuras son más importantes, y algunas escuelas prestigiosas prefieren realizar el examen B-tree. Debido a que los árboles de clasificación binaria y los árboles binarios equilibrados son árboles binarios especiales, están más estrechamente relacionados con los árboles binarios. No es difícil aprender el capítulo del árbol binario aquí.
El árbol de clasificación binaria es simplemente "pequeño izquierdo y grande derecho", y su resultado transversal en orden es una secuencia ordenada creciente. El árbol binario equilibrado es una optimización del árbol de clasificación binario, y su esencia también es un árbol de clasificación binario. Pero un árbol binario equilibrado limita la profundidad de los subárboles izquierdo y derecho: el valor absoluto de la diferencia de profundidad no puede ser mayor que 1. Para los árboles ordenados binariamente, a menudo se prueba el algoritmo de "determinar si un árbol binario es un árbol ordenado binario", que puede ser recursivo o no recursivo. El establecimiento de árboles binarios equilibrados también es un punto que se prueba a menudo, pero este punto de conocimiento se centra en última instancia en los cuatro algoritmos de ajuste de los árboles binarios equilibrados. Por lo tanto, es necesario dominar los cuatro algoritmos de ajuste de los árboles binarios equilibrados. El ajuste es el resultado transversal en orden antes y después del ajuste.
El árbol b es una mejora adicional del árbol de clasificación binario y también puede entenderse como un árbol de clasificación tridente, cuadrúpedo.... Además del algoritmo de búsqueda del árbol B, se debe prestar especial atención a los algoritmos de inserción y eliminación del árbol B. Debido a que estos dos algoritmos implican la división y fusión de nodos del árbol B, son un punto difícil. B-tree es uno de los puntos clave al que deben prestar atención los estudiantes que postulan a escuelas prestigiosas.
El árbol de palabras clave, también llamado árbol de caracteres, es especialmente adecuado para encontrar palabras en inglés. Generalmente, no es necesario describir completamente el código fuente del algoritmo, sino establecer un árbol de claves basado en la idea del algoritmo y describir su proceso de búsqueda aproximado.
3. Algoritmo básico de búsqueda de tablas hash:
La palabra hash es una palabra extranjera, que se traduce de la palabra "hash", que significa: hash o hash. La idea básica de la búsqueda en tabla hash es: de acuerdo con las características de los datos a buscar, diseñar una función con la palabra clave registrada como variable independiente. Una vez que esta función convierte la palabra clave, el resultado de la interpretación es la dirección a. ser buscado. Los puntos de examen basados en la tabla hash incluyen: el diseño de la función hash, la selección del método de resolución de conflictos y la descripción del proceso de manejo de conflictos.
Capítulo 8 Clasificación interna
La clasificación interna es el último capítulo importante del curso de DS. Hay muchos tipos de preguntas basadas en este capítulo: completar espacios en blanco, selección. juicio e incluso grandes preguntas algorítmicas. Pero todo se reduce a un punto: comprobar si está familiarizado con los distintos algoritmos de clasificación y sus ideas contenidas en los libros, así como con sus ventajas, desventajas e indicadores de rendimiento (complejidad temporal).
En este capítulo, nuestro enfoque será diferente al de los capítulos anteriores. Haremos diferentes disposiciones en el capítulo de clasificación a partir de los siguientes aspectos para tener una comprensión más completa de la estructura general y los diversos algoritmos del capítulo de clasificación.
Según el tipo de algoritmo de clasificación, este capítulo explica principalmente los siguientes métodos de clasificación: inserción, selección, intercambio, fusión y conteo.
Entre ellos, la ordenación por inserción se puede dividir en: inserción directa, semiinserción, inserción bidireccional y ordenación Hill. La diferencia más fundamental entre estos algoritmos de ordenación por inserción se reduce a qué reglas se utilizan para encontrar el punto de inserción de nuevos elementos. La inserción directa significa buscar en secuencia y la mitad de inserción significa buscar por la mitad. La clasificación Hill mejora la eficiencia de la clasificación al controlar el incremento del rango total de números involucrados en la clasificación cada vez.
La clasificación de intercambio también se llama clasificación de burbujas. Se puede mejorar sobre la base de la clasificación de intercambio y se puede ordenar rápidamente. La idea de clasificación rápida es una oración: use el número del medio para dividir el conjunto de datos que se va a clasificar en dos. La clasificación rápida, en términos del concepto de "escala del problema", es algo opuesta a la de Hill. La clasificación rápida procesa primero los elementos más grandes y luego reduce gradualmente el tamaño del procesamiento para finalmente lograr el propósito de clasificación.
La clasificación por selección es más difícil que los algoritmos de clasificación anteriores. Específicamente, se puede dividir en: selección simple, selección de árbol y disposición en montón. La diferencia entre estos tres métodos radica en las reglas según las cuales se selecciona el número más pequeño. La selección simple determina el número mínimo a través de un esquema de recorrido de matriz simple; la selección de árbol utiliza una idea similar a un "torneo" para comparar dos números, eliminar continuamente el más grande (pequeño) y finalmente seleccionar el número más pequeño (grande) y ordenar el montón; utiliza la estructura de datos del montón para seleccionar el número más pequeño en la parte superior del montón mediante una serie de operaciones como eliminar y ajustar elementos del montón. La creación y el ajuste del montón en la clasificación del montón son puntos de prueba importantes. La clasificación por selección de árboles también ha aparecido en problemas de algoritmos a gran escala en algunas escuelas, preste atención.
La clasificación por combinación, como su nombre indica, logra el propósito de clasificar mediante la operación de "fusión". Dado que es una fusión, debe ser una colección de dos o más datos para fusionar. Por lo tanto, en la clasificación por combinación, la más popular es la combinación bidireccional. La idea del algoritmo es relativamente simple. Una cosa para recordar es que la clasificación por combinación es una clasificación estable.
La clasificación por base es un método de clasificación muy especial y, precisamente por su particularidad, la clasificación por base es más adecuada para algunas ocasiones especiales, como la clasificación por póquer. La clasificación Radix se divide en dos tipos: clasificación de palabras clave múltiples (clasificación de póquer) y clasificación en cadena (clasificación de números enteros). La idea central de la clasificación de bases es utilizar el concepto de "espacio de bases" para estandarizar y reducir el tamaño del problema durante el proceso de clasificación, siempre que la comparación de palabras clave se realice de acuerdo con la idea de bases. Al ordenar, la secuencia final obtenida es una secuencia ordenada.
Este capítulo trata sobre dominar las ideas, la implementación del pseudocódigo y la complejidad temporal de varios algoritmos de clasificación, así que preste más atención a las especificaciones, el resumen y la comparación al estudiar. Además, la parte 10.7 del libro de texto requiere memorización. Según lo entendido, esta sección casi se ha convertido en un punto de prueba obligatorio para muchas escuelas cada año.
En este punto, se han estandarizado los temas clave en todos los capítulos de la estructura de datos. Los estudiantes que utilizan los libros de texto de Tsinghua Yan pueden consultar los puntos clave que figuran en esta publicación para su revisión. Sin embargo, debido al nivel limitado del autor, es posible que muchos puntos de prueba no estén estandarizados o que algunos puntos de prueba estén estandarizados incorrectamente. Aquí, el autor espera sinceramente que todos los amigos presten atención. Continuaré mejorando y publicando nuevos resúmenes y notas de revisión de estructuras de datos.
Notas sobre la estructura de datos de Yan Weimin
Capítulo 2: Tablas lineales (incluidos ejercicios, respuestas y puntos clave)
-
El El objetivo de este capítulo es dominar varios algoritmos básicos implementados en listas secuenciales y listas enlazadas individualmente y el análisis del rendimiento del tiempo relacionado. La dificultad es utilizar los conocimientos básicos aprendidos en este capítulo para diseñar algoritmos eficaces para resolver problemas de aplicación relacionados con tablas lineales.
El nivel de contenido que requiere es: las características estructurales lógicas de la tabla lineal; las operaciones básicas definidas en la tabla lineal, y las operaciones más complejas se construyen utilizando operaciones básicas.
Los niveles de contenido requeridos incluyen: el significado y las características de las listas de secuencias, el análisis de las operaciones de inserción y eliminación de listas de secuencias y su rendimiento en el tiempo promedio, y la resolución de problemas de aplicación simples.
Cómo las listas enlazadas representan la relación lógica entre elementos en una lista lineal; las diferencias en los métodos de enlace entre listas enlazadas individualmente, listas enlazadas doblemente y listas enlazadas circulares implementadas en forma individual; listas enlazadas, etc. Algoritmos básicos y su complejidad temporal. El puntero de cola en una lista enlazada circular reemplaza al puntero de cabeza, y existen similitudes y diferencias entre el algoritmo en una lista enlazada circular única y el algoritmo correspondiente en una lista enlazada única. La definición de lista doblemente enlazada y algoritmos relacionados. Utilice algoritmos de diseño de listas vinculadas para resolver problemas de aplicaciones simples.
El contenido requerido para alcanzar el nivel es la comparación entre listas secuenciales y listas enlazadas, y cómo elegir una como estructura de almacenamiento para lograr un mejor rendimiento espacio-temporal.
-
Las características de la estructura lógica de las tablas lineales son fáciles de entender. Como sugiere el nombre, su estructura lógica es como una línea con nudos, que es muy vívida. Si hay nudos en esta línea, es una lista no vacía con solo un nodo inicial y un nodo final, y solo hay un nodo antes y después de otros nudos (predecesores directos y sucesores directos).
Las operaciones básicas definidas en tablas lineales incluyen principalmente construir una tabla vacía, encontrar la longitud de la tabla, buscar nodos, buscar, insertar y eliminar.
-
La relación entre la estructura lógica y la estructura de almacenamiento de las tablas lineales. En las computadoras, hay muchas formas de almacenar los nodos de tablas lineales en unidades de almacenamiento. El método más sencillo es almacenarlos en orden. Se almacena en un grupo de unidades de almacenamiento con direcciones consecutivas según la estructura lógica de una tabla lineal. La ubicación física de cada elemento en la unidad de almacenamiento es consistente con la relación adyacente de cada nodo en la estructura lógica.
Las operaciones básicas implementadas en la lista de secuencia analizan principalmente las operaciones de inserción y eliminación. Dominamos algoritmos relevantes a través de la práctica. Para la inserción y eliminación de tablas secuenciales, la complejidad temporal promedio es O (n).
-
La estructura de almacenamiento vinculada de la lista lineal. Es diferente de la lista de secuencia. Una lista vinculada utiliza un conjunto de unidades de almacenamiento arbitrarias para almacenar los nodos de una lista lineal, y estas unidades de almacenamiento se pueden distribuir en cualquier lugar de la memoria. Por lo tanto, el orden lógico y físico de los nodos en una lista enlazada no es necesariamente el mismo. Por lo tanto, para representar correctamente la relación lógica entre nodos, se almacena el valor de cada nodo (es decir,