¿Existen libros de texto sobre estructura de datos (versión en lenguaje C)?
Notas clave para la revisión de la estructura de datos [Aplicable al libro de texto Edición Tsinghua Yan]
1. Estructura de capítulos y componentes clave de la estructura de datos
La división de capítulos de los temas de estructura de datos es básicamente la siguiente: introducción, tablas lineales, pilas y colas, cadenas, matrices multidimensionales y tablas generalizadas, árboles y árboles bifurcados, gráficos. , Búsquedas, permutaciones internas y externas, archivos, asignación de almacenamiento dinámico, filas internas, filas externas, archivos y asignación de almacenamiento dinámico.
Para la gran mayoría de las escuelas, los tres capítulos "Disposición externa, archivos y asignación de almacenamiento dinámico" básicamente no se prueban en el curso de la enseñanza de pregrado en informática en la mayoría de los colegios y universidades, estos tres capítulos tampoco se prueban. No incluido en el examen. Básicamente no se habla de ello. Por lo tanto, no necesitamos gastar demasiada energía en estos tres capítulos, siempre que conozcamos los conceptos básicos. Sin embargo, para los amigos que solicitan ingreso a escuelas prestigiosas, especialmente esta escuela, y aquellos que realizan la evaluación histórica de estos tres capítulos en el examen, entonces se debe prestar atención a estos tres capítulos en esta parte.
Según los capítulos que proporcionamos anteriormente y las introducciones de los siguientes tres capítulos, la proporción de cada capítulo sobre estructura de datos es aproximadamente la siguiente:
Introducción: muy poco contenido, simple conceptos, la mayoría de los puntos Son solo unos pocos puntos y algunas escuelas ni siquiera toman el examen.
Tabla lineal: capítulo básico, uno de los exámenes imprescindibles. La mayoría de las preguntas del examen son preguntas de conceptos básicos. Entre las preguntas del examen de escuelas prestigiosas, hay pocas preguntas de diseño de algoritmos a gran escala. Si es así, se combina con otros capítulos.
Pilas y colas: en los capítulos básicos, es fácil tener problemas conceptuales básicos y debe ser uno de los contenidos del examen. La pila a menudo se examina junto con otros capítulos y, a menudo, se examina junto con conceptos como la recursividad.
Cadena: Capítulo básico, el concepto es relativamente simple. Las preguntas de diseño de algoritmos a gran escala específicamente para este capítulo son relativamente raras, y las más comunes son el análisis de algoritmos basado en KMP.
Matrices multidimensionales y tablas generalizadas
: capítulo básico, las preguntas sobre algoritmos basados en matrices también son comunes y la relación de puntuación fluctúa mucho. ¿Es una "unidad opcional" o una "suplementaria?" problema de unidad". En circunstancias normales, si hay preguntas que hacer, la mayoría de ellas no serán grandes preguntas. Las matrices a menudo se combinan con capítulos como "Búsqueda y clasificación" como puntos de prueba principales.
Árbol y Árbol Binario
: Capítulos claves y difíciles, capítulos requeridos para cada escuela. La diferencia entre las preguntas de cada escuela en este capítulo es si hay una o dos preguntas importantes sobre el diseño de algoritmos en este capítulo. Al analizar los exámenes de muchas escuelas, se descubre que la mayoría de las escuelas tienen un historial de plantear grandes preguntas sobre el diseño de algoritmos en este capítulo.
Imagen: Capítulos clave, pero también capítulos difíciles, especialmente escuelas famosas. Si se utiliza como examen clave, se reflejará más en el análisis y diseño de los tipos de preguntas, que se pueden combinar con los tres capítulos para formar los tipos de preguntas de diseño de las principales preguntas de diseño de algoritmos.
Buscar
: Capítulos clave y difíciles, con muchos conceptos, conexiones estrechas y fácil confusión. Esta pregunta se puede formular como una pregunta de análisis y también es común entre las preguntas de conceptos básicos. Las preguntas de diseño de algoritmos se pueden probar en combinación con matrices o capítulos de árboles.
Ordenar
: similar a la búsqueda de capítulos, este capítulo es clave y difícil, con muchos conceptos y conexiones cercanas, lo que facilita la confusión de conceptos. Al probar conceptos básicos, me gusta especialmente probar preguntas como comparar las ventajas y desventajas de varios algoritmos de clasificación. Si la pregunta sobre el diseño del algoritmo se toma como una sola pregunta, a menudo se prueba en combinación con matrices.
En segundo lugar, se describen los puntos clave del capítulo sobre estructura de datos:
Descripción general del Capítulo 0
Este capítulo desempeña principalmente un papel de liderazgo y proporciona alguna orientación avanzada. para que los lectores aprendan las estructuras de datos. Todos deben prestar atención a los siguientes puntos: los conceptos básicos de estructura de datos, los conceptos y métodos de medición de la complejidad del tiempo y la complejidad del espacio, y las precauciones al diseñar algoritmos. No hay muchos puntos de prueba en este capítulo, solo preste un poco de atención y comprenda.
Capítulo 1 Tablas lineales
Como comienzo de las estructuras lineales, no se puede subestimar el papel de las tablas lineales en el estudio de estructuras lineales e incluso en toda la disciplina de estructuras de datos. En este capítulo, el concepto de almacenamiento en cadena se introduce sistemáticamente por primera vez. No importa qué capítulo involucre el almacenamiento en cadena, el concepto de almacenamiento en cadena será la máxima prioridad de toda la disciplina de estructura de datos.
En general, los puntos clave que se pueden examinar en este capítulo de tablas lineales son los siguientes:
1. Conceptos básicos relacionados con las tablas lineales, tales como: pre-mesa, post-tabla, conceptos como longitud de la tabla, tabla vacía, nodo original, nodo principal, puntero principal, etc.
2. Las características estructurales de las tablas lineales son principalmente: a excepción del primer y último elemento, cada nodo tiene solo un nodo predecesor y un nodo sucesor.
3. Almacenamiento secuencial de tablas lineales y sus dos diferentes métodos de implementación en entornos de lenguaje específicos: asignación estática y asignación dinámica de espacio de tablas. Similitudes y diferencias entre listas enlazadas estáticas y listas secuenciales.
4. Almacenamiento enlazado de listas lineales y las características y operaciones de las siguientes listas enlazadas de uso común: listas enlazadas individualmente, listas enlazadas circulares, listas enlazadas doblemente y listas enlazadas doblemente circulares. 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 doblemente enlazadas y los algoritmos de inserción y eliminación de listas doblemente enlazadas son contenidos de examen más comunes. Además, en los últimos años, ha habido algunas preguntas de prueba en algunas escuelas que requieren el uso de algoritmos recursivos para lograr una salida de lista enlazada individualmente (que puede ser una salida secuencial o una salida invertida).
En las preguntas sobre listas enlazadas, a menudo examinamos: juzgar si la lista está vacía. En diferentes listas vinculadas, los métodos para determinar si la lista está vacía son diferentes, tenga en cuenta.
5. Comparación de las ventajas y desventajas del almacenamiento secuencial en mesa lineal y el almacenamiento en cadena, es decir, sus respectivas aplicaciones. Existen respectivas ventajas de configurar el puntero principal en una lista enlazada individualmente, configurar el puntero de cola y la estructura de almacenamiento de índice en una lista enlazada circular sin configurar un puntero principal.
Capítulo 2: Pilas y colas
Las pilas y colas son el primer obstáculo que encuentran muchos estudiantes que aprenden DS. Muchas personas han estado sentadas en este vagón desde el comienzo de este capítulo. hasta ahora. Por lo tanto, comprender las pilas y las colas es la única forma de convertirse en un maestro de DS.
Antes de estudiar este capítulo, puede preguntarse si ya comprende lo siguiente:
1. Las definiciones de pilas y colas y los conceptos de estructura de datos relacionados, incluidos: pila secuencial, encadenado. pila, pila compartida, cola circular, cola encadenada, etc. Características del acceso a la pila y la cola a los datos (tenga en cuenta que incluye dos partes: almacenamiento y recuperación).
2. Algoritmo recursivo. La relación entre pila y recursividad, y el algoritmo clásico que utiliza la pila para realizar recursividad a no recursividad: 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 la profundidad de recorrido del gráfico y la pila, etc. La mayoría de estos problemas que involucran árboles y gráficos se estudiarán en los capítulos relacionados con árboles y gráficos.
3. Aplicación de la pila: los principios de las expresiones digitales, como corchetes, etc., solo se entienden en principio. En cuanto a los requisitos específicos del diseño de algoritmos, este tema no examina mucho sobre este tema.
4. Algoritmo de entrada y salida de cola circular bajo las condiciones de juzgar si la cola está vacía o llena.
Si ya está familiarizado con los puntos anteriores, no necesita leer el capítulo sobre pilas y colas. Tenga en cuenta que dije que no es necesario que lea el libro, no que no tenga que responder las preguntas.
Capítulo 3 Cuerdas
Después de experimentar el dolor del capítulo de la pila, el capítulo de cuerdas finalmente marcó el comienzo del amanecer.
Las cadenas, conceptualmente hablando, son un capítulo relativamente pequeño y el más fácil de aprender. Sin embargo, como todos sabemos, el algoritmo KMP es un umbral importante para este capítulo. Lo que pasamos fueron las vastas montañas DS. ríos, jaja.
Las principales fortalezas que es necesario superar en el capítulo sobre cadenas:
1. El concepto básico de cadenas y la relación entre cadenas y tablas lineales (las cadenas se refieren a caracteres cuyos los elementos son datos de caracteres) Tabla lineal especial), la diferencia entre cadenas vacías y cadenas espaciales, las condiciones de igualdad de las cadenas
2. Operaciones básicas de las cadenas y el uso de estas funciones básicas, que incluyen: tomar subcadenas. , convertir caracteres Concatenar cadenas en cadenas, reemplazar longitudes de cadenas y más. Operaciones básicas en cadenas y el uso de estas funciones básicas, que incluyen: extracción de subcadenas, concatenación de cadenas, reemplazo de cadenas, longitud de cadenas, etc. El uso de operaciones básicas de cadenas para completar algoritmos específicos es el foco del examen de operaciones básicas de muchas escuelas.
3. Las diferencias, conexiones y métodos de implementación entre cadenas de secuencia, cadenas de cadena y cadenas de bloques.
Idea del algoritmo 4.KMP. Métodos de búsqueda para la siguiente matriz y la matriz nextval en KMP. Aclare las deficiencias de los algoritmos tradicionales de coincidencia de patrones e identifique áreas donde la próxima matriz necesita mejorar. Entre ellos, comprender el algoritmo es el núcleo y ser capaz de encontrar matrices es el punto de puntuación. No hace falta decir que esta parte es el foco de este capítulo. Los posibles métodos de examen son: encontrar el siguiente valor y el valor nextval de la matriz, proporcionar el proceso de coincidencia en función del siguiente valor o el valor nextval de la matriz y utilizar el algoritmo KMP para hacer coincidir.
Capítulo 4 Arreglos y Tablas Generalizadas
Para aquellos de ustedes que han estudiado lenguajes de programación, esta no es la primera vez que ven el concepto de arreglos. Estoy familiarizado con él. la segunda vez, así que conceptualmente no habrá muchos obstáculos. Sin embargo, como curso de posgrado, el enfoque del examen en este capítulo puede ser diferente del de los lenguajes de programación en las universidades, como 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 una estructura lineal, por lo que este capítulo también se clasifica como una estructura lineal.
El enfoque del examen en este capítulo es:
1. Resolver la posición de elementos de una matriz en matrices multidimensionales. Generalmente, primero se dan la dirección del primer elemento de la matriz y el espacio de direcciones ocupado por cada elemento, y las dimensiones de la matriz multidimensional se dan en grupos, y luego se le pide que encuentre la posición de un elemento. en la matriz.
2. Descubra las diferencias y conexiones entre el almacenamiento en filas y el almacenamiento en columnas, y sea capaz de resolver problemas de tipo 1 basándose en estos dos métodos de almacenamiento diferentes.
3. Almacenar los elementos de una matriz especial en una matriz según la disposición adecuada. 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: ternaria, binaria con vectores de fila auxiliares y almacenamiento de listas entrecruzadas. Aprenda algoritmos para convertir triples o pares de matrices dispersas en tablas de unión cruzada.
4. Se debe aclarar el concepto de tablas generalizadas, especialmente las definiciones de encabezados y pies de tabla. Ésta es la base para comprender todo el algoritmo en la parte de la tabla generalizada. Recientemente, en algunas escuelas, existe un tipo de pregunta de este tipo: dada una determinada tabla generalizada L, se realizan varias operaciones en los valores de las cadenas de cabeza y cola, y es necesario encontrar la tabla generalizada L original. .
5. Algoritmos recursivos relacionados con tablas generalizadas. Dado que la definición de tablas generalizadas es recursiva, los algoritmos relacionados con tablas generalizadas suelen ser recursivos. Por ejemplo: encontrar la profundidad de una tabla, copiar una tabla generalizada, etc. En esta pregunta, se pueden usar dos métodos diferentes para responder a esta pregunta según diferentes puntos de vista sobre tablas generalizadas: uno es considerar una tabla generalizada como dos partes: el encabezado y la cola, y operar en el encabezado y la cola respectivamente; es tratar una tabla generalizada como un encabezado y una cola. Una tabla generalizada se considera como varias subtablas y las operaciones se realizan en cada subtabla por separado.
Capítulo 5 Árboles y árboles binarios
De aprender estructuras lineales a aprender estructuras de árboles es un salto en el estudio de los cursos de estructura de datos, ya sea que este salto se complete bien o no, lo será. estar directamente relacionado con si puede lograr puntajes altos en el examen real y, en última instancia, todo esto afectará el puntaje general de su curso profesional. Por tanto, la importancia del árbol en este capítulo es evidente.
En general, los puntos de conocimiento en este capítulo sobre árboles incluyen principalmente: 1:
El concepto, las propiedades y la estructura de almacenamiento de los árboles binarios, tres algoritmos para el recorrido del árbol binario (algoritmo recursivo y algoritmo no recursivo), otros algoritmos para implementar árboles binarios basados en tres algoritmos transversales básicos, el concepto de agrupación de árboles binarios y algoritmos para agrupar árboles binarios, y el algoritmo de búsqueda posterior para agrupar árboles binarios, el concepto, composición y aplicación. de árboles binarios óptimos, conceptos de árboles y formas de almacenamiento, algoritmos de recorrido de árboles y bosques y su conexión con algoritmos de recorrido de árboles binarios, conversión de árbol a bosque y árbol binario.
Echemos un vistazo a los principales métodos de prueba para los puntos de conocimiento anteriores:
1. El concepto, las propiedades y la estructura de almacenamiento de los árboles binarios
Los métodos de examen pueden incluir: examinar directamente la definición de árboles binarios, para explicar la diferencia entre los árboles binarios y los árboles ordinarios de dos ramas; examinar las propiedades; de árboles binarios completos y árboles binarios completos, y las características de los árboles binarios ordinarios Cinco propiedades: el número máximo de nodos en la i-ésima capa, el número máximo de nodos en un árbol binario con profundidad k, la propiedad de n0=n2 1, la profundidad de un árbol binario completo con n nodos, la distancia entre un nodo secundario y su nodo principal cuando se almacena un árbol binario en orden La relación de sustitución (lado izquierdo: 2 * i, lado derecho: 2 * i 1).
Las respectivas ventajas, desventajas y ocasiones aplicables del almacenamiento de listas enlazadas secuenciales y el almacenamiento de listas enlazadas binarias de árboles binarios, y la representación de listas enlazadas ternarias de árboles binarios.
2. Tres algoritmos transversales para árboles binarios
La calidad de este punto de conocimiento estará directamente relacionada con la comprensión del algoritmo de los capítulos del árbol y, además, con la comprensión del árbol. capítulos.Si el problema de diseño del algoritmo se puede completar con éxito. Hay tres algoritmos de recorrido de árbol binario: primer orden, orden medio y orden de cola. La base para la división es el orden en el que se accede a los datos del nodo raíz en cada algoritmo. No solo es necesario dominar los tres algoritmos transversales recursivos y comprender los pasos reales para realizar estos algoritmos, sino que también es necesario dominar los tres algoritmos transversales no recursivos. Debido a que muchos de los algoritmos del capítulo sobre árboles binarios se pueden transformar directamente a partir de tres algoritmos recursivos (como encontrar el número de hojas), después de dominar los tres algoritmos transversales no recursivos, puede resolver problemas como: "Usar no -Algoritmo recursivo para encontrar el número de hojas de un árbol binario". Proporcionaré las versiones de memoria de los tres algoritmos transversales recursivos y no recursivos en otra serie de artículos (/ibbs.dll?bbsdisp?t_id=301583amp; bp=2amp; bt=0. Asegúrese de memorizarlos).
3. Otros algoritmos de árbol binario se pueden completar de acuerdo con tres transformaciones de algoritmo transversal:
Encuentre el número de hojas, encuentre el número total de nodos del árbol binario, encuentre el número total de Nodos de 1 o 2 grados, copie el árbol binario e intercambie los subárboles izquierdo y derecho del árbol binario, encuentre los valores de n nodos especificados, elimine los valores de n nodos especificados, etc. Si puede dominar los algoritmos transversales recursivos y no recursivos de los árboles binarios, entonces resolver los problemas anteriores es pan comido.
4. Árbol binario de pistas:
El árbol binario de pistas se introduce para evitar soluciones recursivas como el recorrido del árbol binario. Como todos sabemos, aunque la recursividad puede comprender mejor la forma, consumirá muchos recursos de memoria. Si hay muchos niveles de recursividad, inevitablemente traerá el peligro de agotamiento de recursos. Para evitar esta situación, el árbol binario de pistas. Apareció en el salón sagrado. 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 posteriores a la pista y otros problemas algorítmicos de los árboles binarios de pistas básicos (como: encontrar el nodo anterior o el nodo sucesor de un nodo especificado en un determinado tipo de árbol binario de pistas (Preguntas frecuentes).
5. Árbol binario óptimo (árbol de Huffman):
El árbol binario óptimo es una estructura de árbol binario especial introducida para resolver un problema específico. Su premisa es cada borde. Se le da un peso para minimizar la suma de los pesos del árbol binario formado. En la sección del árbol binario óptimo, hay muy pocos algoritmos que prueben directamente el código fuente. Por lo general, 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 mínima de sus pesos. Este tipo de preguntas no es Difícil, sólo haz una pregunta.
6. Árboles y bosques:
Los árboles binarios son un tipo de árbol especial. Esta particularidad no sólo se debe a que tiene hasta 2 ramas, sino que también es la más importante. El punto es: ¡los árboles binarios están ordenados! En otras palabras, los subárboles izquierdo y derecho de un árbol binario no se pueden intercambiar. Si se intercambian, se convertirán en otro árbol binario. De esta manera, pensamos que el árbol binario intercambiado y el árbol binario original no son el mismo. árbol. Sin embargo, para un árbol binario ordinario, no tiene esta propiedad.
El recorrido de árboles y bosques no es tan rico como el de los árboles binarios. Solo tienen dos algoritmos de recorrido: recorrido de raíz primero y recorrido de raíz posterior (para los bosques, esto se llama: primer orden). transversal y transversal posterior al orden).
En los exámenes más difíciles, hay expansiones basadas en estos dos algoritmos, lo que requiere que uses estos dos algoritmos para diseñar otros algoritmos. Sin embargo, este tipo de método de prueba rara vez está disponible en las universidades comunes. Como máximo, solo requiere que escribas. su propia secuencia transversal basada en la primera o segunda raíz. Los dos primeros y segundos recorridos de raíz corresponden al algoritmo de recorrido de árbol binario: el primer recorrido de raíz corresponde al primer orden del recorrido de árbol binario y el segundo recorrido de raíz corresponde al orden intermedio del recorrido de árbol binario. Esto se ha convertido en un punto de prueba en muchas escuelas, y los métodos de prueba también son diferentes. Algunos prueban directamente esta oración y otros le piden que resuelva la secuencia transversal y luego responda la pregunta. Los árboles binarios, los árboles y los bosques corresponden a listas binarias enlazadas. Un árbol binario usa una lista binaria vinculada para almacenar sus hijos izquierdo y derecho. Un árbol usa una lista binaria vinculada para almacenar sus hijos y hermanos (llamada lista vinculada hijo-hermano). Un bosque también usa una lista binaria vinculada para almacenar sus hijos. hijos y hermanos.
Cada parte del capítulo del árbol es un punto clave y cada paso es un punto de prueba. Debemos pasar cada prueba una por una.
Capítulo 6 Gráficos
Si la transición del estudio de estructuras lineales a estructuras de árbol es la sublimación de la investigación de la organización de datos en la disciplina de estructura de datos, entonces la transición del estudio de estructuras de árbol al estudio de gráficos estructuras La transformación nos muestra además el importante papel de las estructuras de datos en la resolución de problemas prácticos.
Este capítulo sobre gráficos se caracteriza por conceptos amplios, 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 examen. , es casi inimaginable no examinar el conocimiento de los dos capítulos de árboles y gráficos.
Echemos un vistazo a los principales puntos de prueba en el capítulo de gráficos y los métodos de prueba para estos puntos de prueba:
1. Preguntas para probar los conceptos básicos de gráficas:
Estos conceptos son la base para estudiar el capítulo de gráficas. Los conceptos de este capítulo incluyen: la definición y características de gráficas, gráficas no dirigidas, gráficas dirigidas, en grado. , grado externo, conceptos como gráficos completos, subgrafos generados, longitudes de ruta, ciclos, gráficos (fuertemente) conectados, gráficos (fuertemente) conectados, componentes (fuertemente) conectados, etc. También se deben dominar las cuestiones computacionales relacionadas con estos conceptos.
2. Examen de 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. En el examen, algunas escuelas proporcionan un formulario de almacenamiento y requieren que los candidatos utilicen un algoritmo o escriban manualmente otro formulario de almacenamiento del gráfico basado en la estructura dada.
3. Examen de dos algoritmos de recorrido: recorrido en profundidad y recorrido en amplitud
El recorrido en profundidad y el recorrido en amplitud son los dos algoritmos transversales básicos para gráficos. Estos dos algoritmos son muy útiles para gráficos. El examen de este capítulo es tan importante como el examen del capítulo "recorrido de primer, medio y último orden" sobre árboles binarios. En el examen, las preguntas de diseño de algoritmos en este capítulo de gráficos a menudo se basan en estos dos algoritmos transversales básicos, como "el problema de encontrar el camino más largo y el más corto" y "determinar si existe un camino simple entre dos vértices de longitud". K". El algoritmo de recorrido en amplitud y el algoritmo de recorrido en profundidad se utilizan respectivamente.
4. Los conceptos de árbol de expansión, árbol de expansión mínimo y construcción de á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, se requiere escribir su proceso de construcción y el árbol de expansión mínimo generado final basado en las ideas de los dos. Algoritmos de árbol de expansión mínimo.
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 convergencia directa y el otro es el algoritmo de primer vértice sin sucesor. . En otras palabras, uno es la clasificación "antes y después", y el otro es la clasificación "antes y después". Por supuesto, el resultado de esta última clasificación es la "clasificación topológica inversa".
6. Problema de ruta crítica:
Este problema es el más difícil en el capítulo de gráficos. Hay tres aspectos clave para comprender la ruta crítica: primero, qué es la ruta crítica, segundo, qué significa el tiempo más antiguo y cómo encontrarlo, y tercero, qué significa el tiempo más reciente y cómo encontrarlo. En pocas palabras, la hora más temprana se resuelve mediante el método "de adelante hacia atrás", y la última hora se resuelve mediante el método "de atrás hacia adelante". Además, si desea encontrar la última hora, debe buscarla. todos los primeros tiempos después de pedirlo.
Este problema generalmente no se usa para probar directamente el código fuente del algoritmo. Generalmente es necesario resolverlo de acuerdo con el proceso del algoritmo y los pasos descritos en el libro.
Al diseñar el algoritmo de ruta crítica, también debe prestar atención a los siguientes puntos: cuando se utiliza la estructura de almacenamiento de la lista de adyacencia, la hora más temprana y la más reciente deben usarse de diferentes maneras, es decir: en el algoritmo inicial, primero debe establecer el tiempo más temprano del vértice 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. El problema del camino más corto:
El problema del camino más corto:
Junto con el problema del camino crítico, se les llama los dos obstáculos del sello. . La comprensión conceptual es relativamente fácil, la clave es la comprensión del algoritmo. Hay dos tipos de problemas de camino más corto: uno es encontrar el camino más corto desde un punto a otros puntos; el otro es encontrar el camino más corto entre cada par de vértices en el gráfico. Este problema también tiene un trasfondo muy práctico. El problema típico debería ser la selección de atracciones turísticas y rutas turísticas. El algoritmo DIJSKTRA se utiliza para resolver el primer problema y el algoritmo FLOYD para resolver el segundo problema. Tenga en cuenta la diferencia entre los dos.
Capítulo 7 Búsqueda
En bastantes libros de texto sobre estructuras de datos, la búsqueda y la clasificación se clasifican como estructuras de datos avanzadas. Cabe decir que los dos capítulos de búsqueda y clasificación son una síntesis del conocimiento que hemos aprendido anteriormente. No solo utilizan árboles, sino también listas vinculadas y otros conocimientos. El uso de ciertos aspectos de estas estructuras de datos constituye 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 texto de documentos hasta la búsqueda en Internet durante la mayor parte de nuestro tiempo.
Al revisar el conocimiento de este capítulo, primero debe aclarar los siguientes conceptos:
El significado de las palabras clave, palabras clave de primer nivel y palabras clave de segundo nivel; las diferencias entre la búsqueda estática; y búsqueda dinámica Significado y diferencia, se debe tener en cuenta el concepto de longitud de búsqueda promedio ASL y sus métodos de cálculo y resultados de cálculo 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: Categoría 1, búsqueda en tablas de secuencia; Categoría 2, búsqueda en tablas de árbol; Categoría 3, búsqueda en tablas hash. La siguiente es una introducción detallada a los puntos de conocimiento y métodos de prueba:
1. Búsqueda en tablas lineales:
Se divide principalmente en tres estructuras lineales: tabla de secuencia, secuencia ordenada. tabla, índice Tabla de secuencia. Para el primero utilizamos el método de búsqueda tradicional y los comparamos uno por uno. Para listas secuenciales ordenadas, utilizamos el método de búsqueda binaria. 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 y la implementación de los tres algoritmos en estas tres tablas. Entre ellos, la búsqueda binaria también debe prestar especial atención a las condiciones aplicables y su implementación recursiva.
2. Búsqueda en la tabla de árbol:
Este es el enfoque y la dificultad de este capítulo. Debido a que el contenido presentado en esta sección utiliza tablas de árbol para la búsqueda, es fácil confundirlo con cierto concepto de árbol. El contenido de esta sección está relacionado con el contenido del capítulo del árbol, pero existen muchas diferencias que conviene estandarizar. Las tablas de árbol se dividen principalmente en los siguientes tipos: árbol de clasificación binaria, árbol binario equilibrado, árbol B y árbol de claves. Entre ellos, especialmente las dos primeras estructuras, algunas escuelas prestigiosas prefieren realizar el examen B-tree. Debido a que los árboles de clasificación binaria y los árboles binarios equilibrados son tipos especiales de árboles binarios, están estrechamente relacionados con los árboles binarios. Si ha aprendido este capítulo sobre árboles binarios, no será difícil aquí.
El árbol de clasificación binaria, en resumen, es "pequeño a la izquierda y grande a la derecha". El resultado de su recorrido es una secuencia ordenada con orden creciente en el medio. 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. Sin embargo, el árbol binario equilibrado tiene un límite en la profundidad de los subárboles izquierdo y derecho: el valor absoluto de la diferencia de profundidad debe. no ser mayor que 1. Para los árboles de clasificación binaria, a menudo se estudia el algoritmo de "determinar si un árbol binario es un árbol de clasificación binaria", que puede ser recursivo o no recursivo. Ya sea recursivo o no recursivo. El establecimiento de árboles binarios equilibrados también es un punto de prueba común, pero este punto de conocimiento se centra en última instancia en los cuatro algoritmos de ajuste de los árboles binarios equilibrados. Por lo tanto, debe dominar los cuatro algoritmos de ajuste de los árboles binarios equilibrados. Al realizar el ajuste, puede consultar. : Los resultados del recorrido intermedio antes y después del ajuste son los mismos.
El árbol B es una mejora adicional del árbol de clasificación binaria. El árbol B también puede entenderse como tres bifurcaciones, cuatro bifurcaciones... Árbol de clasificación. Además del algoritmo de búsqueda del árbol B, también 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, es 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 claves, también conocido como árbol de caracteres, es especialmente adecuado para buscar palabras en inglés. Generalmente, no es necesario describir completamente el código fuente del algoritmo. Se trata principalmente de construir un árbol de claves basado en la idea del algoritmo y describir su proceso de búsqueda general.
3. Algoritmo básico para la búsqueda de tablas hash:
"Hash" es una palabra extranjera, traducida de "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 actuales a buscar, utilizando las palabras clave registradas como variables independientes, diseñar una función que convierta las palabras clave e interprete el resultado de la dirección a buscar. Los puntos de prueba 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 DS. Hay muchos tipos de exámenes basados en este capítulo: preguntas para completar los espacios en blanco. preguntas de opción múltiple, preguntas de verdadero-falso e incluso preguntas de algoritmos a gran escala. Sin embargo, en el análisis final, depende de si comprende los diversos algoritmos de clasificación y sus ideas en el libro, así como sus ventajas, desventajas e indicadores de rendimiento (complejidad del tiempo).
En este capítulo, nos centraremos en la explicación de una manera diferente a los capítulos anteriores. Para tener una comprensión más completa de la estructura general y el algoritmo de clasificación de capítulos, comenzaremos con los siguientes aspectos y aprenderemos a clasificar capítulos de diferentes maneras.
Desde la perspectiva de los tipos de algoritmos de clasificación, este capítulo presenta principalmente los siguientes métodos de clasificación: cinco métodos de clasificación: inserción, selección, intercambio, fusión y conteo.
Entre ellos, la clasificación por inserción se puede dividir en: inserción directa, inserción medio plegada, inserción bidireccional y clasificación Hill. La diferencia más fundamental entre estos algoritmos de ordenación por inserción es qué reglas se utilizan en última instancia para encontrar el punto de inserción de un nuevo elemento. La inserción directa es una búsqueda secuencial y la inserción a la mitad es una búsqueda a la mitad. La clasificación Hill logra el propósito de mejorar la eficiencia de la clasificación controlando el rango total de números involucrados en cada clasificación para aumentar de "pequeño a grande".
La clasificación por intercambio, también conocida como clasificación por burbujas, se puede mejorar basándose en la clasificación por intercambio para obtener una clasificación rápida. La idea de clasificación rápida se puede resumir en pocas palabras: dividir el conjunto de datos ordenado por el número del medio en dos. La clasificación rápida es algo opuesta a Hill en el concepto de lidiar con la "escala del problema". La clasificación rápida primero procesa una escala mayor, luego reduce gradualmente la escala de procesamiento y finalmente logra el propósito de clasificar.
La clasificación selectiva 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 clasificación en montón. La diferencia entre estos tres métodos son las reglas utilizadas para seleccionar el número más pequeño. La selección simple consiste en determinar el número mínimo a través de un esquema de recorrido de matriz simple; la selección de árbol consiste en utilizar una idea similar a un "torneo" para comparar los dos números con el número más grande (más pequeño) y, finalmente, seleccionar el número más pequeño (más grande); La clasificación del montón utiliza la naturaleza de la estructura de datos del montón para seleccionar el número más pequeño y colocarlo en la parte superior del montón mediante una serie de operaciones como eliminar y ajustar elementos del montón. En la clasificación del montón, el establecimiento y el ajuste del montón son muy importantes. La clasificación por selección de árboles también ha aparecido en algunas preguntas de algoritmos importantes en algunas escuelas.
La clasificación por fusión, como sugiere el nombre, es lograr el propósito de ordenar mediante la operación de "fusión". Dado que es una fusión, se deben fusionar más de dos conjuntos de datos. Por lo tanto, en la ordenación por fusión, la más preocupante es la fusión bidireccional. La idea del algoritmo es relativamente simple, pero hay una cosa a tener en cuenta: la clasificación sumergida es una clasificación estable.
La clasificación por base es un método de clasificación muy especial y, precisamente debido a su especialidad, la clasificación por base es más adecuada para algunas ocasiones especiales, como los problemas de clasificación de cartas de póquer. La clasificación por base se divide en dos tipos: clasificación de palabras clave múltiples (clasificación de naipes) y clasificación en cadena (clasificación de números enteros).
La idea central de la clasificación por bases es utilizar el concepto de "espacio de bases" para estandarizar y reducir el tamaño del problema. Además, durante el proceso de clasificación, siempre que exista la idea de clasificación por bases. no es necesario comparar palabras clave. De esta forma, la secuencia final obtenida es una secuencia ordenada.
Se debe dominar la complejidad temporal de las ideas de varios algoritmos de clasificación en este capítulo, así como la implementación del pseudocódigo, y se debe prestar más atención a la regularización, el resumen y la comparación durante el estudio. Además, debe estar familiarizado con la Sección 10.7 del libro de texto. Sobre la base de la comprensión y la memorización, esta sección casi se ha convertido en una prueba obligatoria en muchas escuelas cada año.
En este punto, hemos estandarizado los temas clave en todos los capítulos del capítulo de estructura de datos. Los estudiantes que usan la versión del libro de texto de Tsinghua Yan pueden consultar los puntos de revisión proporcionados en esta publicación mientras revisan. Sin embargo, debido al nivel limitado del autor, es posible que haya muchos puntos de prueba que no se hayan estandarizado y que algunos puntos de prueba estén mal estandarizados. Aquí, el autor espera sinceramente que todos los amigos expresen sus preocupaciones con franqueza. El autor continuará mejorando y publicando nuevos datos. Resumen y notas de la revisión de la estructura
Notas básicas de Yan Weimin sobre la estructura de datos, Parte 2
Capítulo 2: Tablas lineales (incluidos ejercicios, respuestas, y puntos clave)
--- ------------------------------------ -------------- --------------------------
El enfoque de Este capítulo es para dominar varias funciones implementadas en listas de secuencias y listas enlazadas individualmente. Algoritmos básicos y análisis de rendimiento de tiempo relacionados. La dificultad es utilizar los conocimientos básicos aprendidos en este capítulo para diseñar algoritmos eficientes para resolver problemas de aplicación relacionados con tablas lineales.
Los requisitos en el nivel de
El contenido requerido para alcanzar el nivel de aplicación integral gt; incluye: el significado y las características de las tablas de secuencia, el análisis de las operaciones de inserción y eliminación de las tablas de secuencia y su rendimiento en el tiempo promedio, y la resolución de problemas de aplicación simples. .
Cómo la tabla de unión representa la relación lógica entre los elementos de la tabla lineal; las diferencias en los métodos de conexión entre tablas de unión simple, tablas de unión doble y tablas de unión circular, creación y búsqueda implementadas en tablas de unión única; Algoritmos básicos de inserción y eliminación y su complejidad temporal. En una lista enlazada circular, el puntero de cola reemplaza al puntero de cabeza, y las 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. Diseñe algoritmos que utilicen listas enlazadas para resolver problemas de aplicaciones simples.
El requisito a nivel <
------------------------------------------- ----- -------------------------------------
Lógico Características estructurales de las tablas lineales. Como sugiere el nombre, es como una línea con un nudo. Si hay un nudo en la línea, entonces es una lista no vacía. Solo puede tener un nodo inicial, solo un nodo final y otros nodos Solo puede haber un nodo adyacente antes y después (nodo predecesor directo y nodo sucesor directo).
Las operaciones básicas definidas en tablas lineales incluyen construir una tabla vacía, encontrar la longitud de la tabla, buscar nodos, buscar, insertar y eliminar.
------------------------------------------- ----- -------------------------------------
El Estructura lógica y suma de tablas lineales. Relaciones entre estructuras de almacenamiento. En las computadoras, hay muchas formas de almacenar los nodos de una tabla lineal en unidades de almacenamiento. El método más simple es almacenarlos en secuencia. Es decir, se almacenan en un grupo de unidades de almacenamiento con direcciones consecutivas según la estructura lógica de la tabla lineal. La ubicación física de los elementos en la unidad de almacenamiento es consistente con la relación adyacente de los nodos en la estructura lógica.
Se analizan las operaciones básicas como la inserción y eliminación implementadas en tablas de secuencia. Dominamos los algoritmos a través de la práctica. Para las operaciones de inserción y eliminación en una tabla secuencial, la complejidad temporal promedio es O (n).
------------------------------------------- ----- -------------------------------------
Enlazado Almacenamiento de estructura de mesas lineales. Se diferencia de una lista secuencial en que una lista enlazada almacena los nodos de una lista lineal en un conjunto de unidades de almacenamiento arbitrarias que 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, mientras se almacena el valor de cada nodo, también se debe almacenar la información de dirección de sus nodos posteriores (es decir,