Acerca de los problemas de estructura de datos, descritos en lenguaje C

Notas resumidas clave de la revisión de la estructura de datos [edición Tsinghua Yan Weimin]

Notas resumidas clave de la revisión de la estructura de datos [Adecuado para el libro de texto de la edición Tsinghua Yan]

1. estructura Estructura del capítulo y componentes clave

Los capítulos del tema de estructura de datos se dividen básicamente en: introducción, tablas lineales, pilas y colas, cadenas, matrices 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 gran mayoría de las escuelas, los tres capítulos de "subcontratación, archivos y asignación dinámica de almacenamiento" básicamente no se prueban en el proceso de enseñanza de pregrado en informática de la mayoría de los colegios y universidades, estos tres capítulos tampoco se prueban. Básicamente no se dan conferencias. Por lo tanto, no es necesario que gastes demasiada energía en estos tres capítulos, siempre que conozcas los conceptos básicos. Sin embargo, si está postulando para una escuela prestigiosa, especialmente si la escuela tiene un historial de evaluación de estos tres capítulos en el examen, entonces estos amigos deben prestar atención a estos tres capítulos.

Según los capítulos que hemos dado anteriormente y la introducción a los últimos tres capítulos, la proporción de capítulos sobre estructuras de datos es aproximadamente la siguiente:

Introducción: muy poco contenido, simple conceptos, y la mayoría de los puntajes son solo unos pocos. Algunas escuelas ni siquiera toman el examen.

Tabla lineal: un capítulo básico, uno de los contenidos obligatorios. 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 lo hay, también se combina con el contenido de otros capítulos.

Stack and Queue: Capítulo básico, preguntas de conceptos básicos fáciles de formular, uno de los exámenes imprescindibles. La pila a menudo se examina junto con otros capítulos y, a menudo, se examina en relación con conceptos como la recursividad.

Cadena: Capítulo básico, el concepto es relativamente simple. Hay muy pocas preguntas de diseño de algoritmos a gran escala específicamente para este capítulo. 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 proporción de fracciones fluctúa mucho, que es una "unidad opcional" o "hou" de la pregunta. Generalmente, si hay preguntas, 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 prueba importante.

Árbol y árbol binario

: Capítulos claves y difíciles, capítulos requeridos para cada escuela. La diferencia en las preguntas formuladas por cada escuela en este capítulo radica en si en este capítulo se formulan una o dos preguntas importantes sobre el 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 plantear grandes preguntas de diseño de algoritmos en este capítulo.

Imagen: Capítulos clave y difíciles, especialmente a las escuelas famosas les encanta hacer exámenes. Si se toma como el foco de la prueba, aparecerá principalmente en las preguntas de análisis y diseño, y puede formar el diseño de la pregunta de diseño del algoritmo junto con el capítulo del árbol.

Buscar

: Los capítulos clave y difíciles tienen muchos conceptos, están estrechamente relacionados y se confunden fácilmente. Las preguntas pueden presentarse como preguntas analíticas y también son comunes entre las preguntas de conceptos básicos. Las preguntas de diseño de algoritmos se pueden probar en combinación con matrices o en combinación con el capítulo del árbol.

Ordenar

: similar a buscar un capítulo, este capítulo también es un capítulo clave y difícil, con más conceptos y conexiones más estrechas, lo que facilita la confusión de conceptos. Al examinar conceptos básicos, me gusta especialmente examinar cuestiones como la comparación de las ventajas y desventajas de varios algoritmos de clasificación. En las principales cuestiones de diseño de algoritmos, si es una cuestión, a menudo se prueba en combinación con matrices.

2. Puntos clave de cada capítulo de estructura de datos:

Descripción general del Capítulo 0

Este capítulo desempeña principalmente un papel principal y ayuda a los lectores a aprender la estructura de datos. Se hicieron algunos preparativos preliminares. Todos prestan atención principalmente 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 el 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 para comprenderlo.

Capítulo 1 Tablas lineales

Como capítulo inicial de las estructuras lineales, no se puede subestimar el papel de las tablas lineales en el estudio de las estructuras lineales e incluso en toda la disciplina de la estructura de datos. En este capítulo, el concepto de almacenamiento en cadena se introduce sistemáticamente por primera vez. El concepto de almacenamiento en cadena será la máxima prioridad de toda la disciplina de estructura de datos, sin importar qué capítulo involucre este concepto.

En general, los puntos de prueba importantes para el examen en el capítulo sobre tablas lineales incluyen los siguientes aspectos:

1. Conceptos básicos relacionados con las tablas lineales, tales como: predecesor, sucesor, tabla Lista larga y vacía, primer nodo, nodo principal, puntero principal y otros conceptos.

2. Las características estructurales de las tablas lineales se refieren principalmente a: a excepción del primer y último elemento, cada nodo tiene un solo predecesor y un solo sucesor.

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 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 las listas enlazadas doblemente circulares son métodos de examen relativamente comunes. Además, en los últimos años, en muchas escuelas han aparecido repetidamente problemas que requieren el uso de algoritmos recursivos para implementar la salida de lista enlazada individualmente (que puede estar en orden secuencial o inverso).

En el tipo de lista vinculada de preguntas pequeñas, a menudo recibimos algunas preguntas como: juzgar si la tabla está vacía. En diferentes listas vinculadas, la forma de determinar si la lista está vacía es diferente, preste atención.

5. En el caso del almacenamiento secuencial de mesa lineal y el almacenamiento en cadena, compare sus diferentes ventajas y desventajas, es decir, sus respectivas ocasiones aplicables. Los beneficios respectivos de configurar el puntero principal en una lista enlazada individualmente, configurar el puntero final sin configurar el puntero principal en una lista enlazada circular y la estructura de almacenamiento del índice.

Capítulo 2 Pilas y colas

Las pilas y colas son el primer obstáculo para muchos estudiantes que aprenden DS. Muchas personas comienzan a marearse con este capítulo y continúan desmayándose. 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 conoce los siguientes puntos:

1. Las definiciones de pilas y colas y los conceptos de estructuras de datos relacionadas, incluidos: Secuencial. pila, pila en cadena, pila compartida, cola circular, cola en cadena, etc. Características del acceso a datos de pila y cola (tenga en cuenta que incluye dos partes: almacenamiento y recuperación).

2. Algoritmo recursivo. La relación entre la pila y la recursividad, y los algoritmos clásicos que utilizan la pila para convertir la recursión en no recursiva: problema factorial n!, problema de secuencia fib, problema de hanoi, problema de mochila, problemas transversales recursivos y no recursivos de árboles binarios, recorrido en profundidad de gráficos y relaciones de pila, etc. Entre ellos, las cuestiones relacionadas con árboles y gráficos se examinarán principalmente en los capítulos correspondientes sobre árboles y gráficos.

3. Aplicación de la pila: los principios de resolución de expresiones numéricas, paréntesis, etc. solo se entienden en principio. No hay muchas preguntas de diseño de algoritmos que requieran probar específicamente este tema.

4. Determine las condiciones para las colas vacías y llenas en la cola circular, y el algoritmo para entrar y salir de la cola en la cola circular.

Si ya conoces bien los puntos anteriores, no necesitas leer el capítulo sobre pilas y colas. Tenga en cuenta que dije que no es necesario leer el libro, no que no es necesario responder las preguntas.

Capítulo 3 Chuan

Después de experimentar el doloroso sufrimiento del primer capítulo de la pila, finalmente llegó el oscuro futuro del primer capítulo de Chuan.

String es un capítulo relativamente pequeño en concepto, y también es uno de los capítulos más fáciles de aprender por uno mismo. Sin embargo, como todos los que han venido aquí saben, el algoritmo KMP es un obstáculo importante en este capítulo. Superando este obstáculo Finalmente, cuando pasamos, volvimos a ver las hermosas montañas y ríos con vastas llanuras, jaja.

Las principales fortalezas que deben superarse en el Capítulo de Cadenas son:

1. El concepto básico de cadenas, la relación entre cadenas y tablas lineales (las cadenas son elementos lineales especiales cuyos todos los elementos son tablas de datos de caracteres), la diferencia entre cadenas vacías y cadenas de espacio, condiciones para la igualdad de cadenas

2. Operaciones básicas en cadenas y el uso de estas funciones básicas, que incluyen: tomar subcadenas y concatenar cadenas. , reemplazando cadenas y encontrando cadenas. Larga espera. 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. La diferencia y conexión entre cadena de secuencia, cadena de cadena y cadena de bloque, y cómo implementarlas.

Idea del algoritmo 4.KMP. Cómo encontrar la siguiente matriz y la matriz nextval en KMP.

Aclare las deficiencias del algoritmo de coincidencia de patrones tradicional y aclare que es necesario mejorar la siguiente matriz. Entre ellos, comprender los algoritmos es el núcleo y ser capaz de encontrar matrices es el punto de puntuación. No hace falta decir que esta sección es el foco de este capítulo. Los posibles métodos de examen son: encontrar los valores de la matriz next y nextval, y realizar el proceso de coincidencia utilizando el algoritmo KMP en función de los valores de la matriz next o nextval obtenidos.

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 vemos el concepto de arreglos. Deberíamos estar familiarizados con él. la segunda vez. Entonces, conceptualmente, no habrá muchos obstáculos. Sin embargo, como curso de posgrado, el enfoque de este capítulo puede ser diferente del de los lenguajes de programación en las universidades, que se presentará a continuación.

El concepto de tabla generalizada apareció por primera vez en la estructura 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 incluye en la estructura lineal.

Los puntos clave del examen en este capítulo son:

1. Resolver la posición de un elemento de matriz en una matriz multidimensional. Generalmente, la dirección del primer elemento del elemento de la matriz y el espacio de direcciones ocupado por cada elemento se dan junto con las dimensiones de la matriz multidimensional, y luego se le pide que encuentre la ubicación de un elemento en la matriz.

2. Aclarar la diferencia y la conexión entre el almacenamiento en filas y el almacenamiento en columnas, y poder resolver el tipo de preguntas en 1 de acuerdo con 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. Familiarizado con los tres métodos diferentes de almacenamiento de matrices dispersas: triplete, triplete binario con vector de fila auxiliar y almacenamiento de lista enlazada cruzada. Domine el algoritmo para convertir triples o tuplas de matrices dispersas en listas entrecruzadas.

4. El concepto de tabla generalizada, especialmente la definición de encabezado y pie de tabla, debe definirse claramente. Este punto es la base para comprender todo el algoritmo de tabla generalizada. Recientemente, en algunas escuelas, ha aparecido un tipo de pregunta: dados los valores de cadena después de varias operaciones de cabeza y cola de una determinada tabla generalizada L, es necesario encontrar la tabla generalizada original L. Todos deberían prestar atención.

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 tablas generalizadas, etc. Este tipo de pregunta se puede responder de dos maneras diferentes según la forma de expresión de la tabla generalizada desde diferentes ángulos: una es considerar una tabla generalizada como dos partes: encabezado y pie de página, y operar en el encabezado y pie de página respectivamente; el segundo es Piense en una tabla generalizada como varias subtablas y opere cada subtabla por separado.

Capítulo 5 Árboles y árboles binarios

La transición del estudio de estructuras lineales al estudio de estructuras de árboles es un salto en los cursos de estudio de estructuras de datos. Este salto se completa. La calidad de su examen estará directamente relacionada con si puede obtener puntajes altos en el examen real y, en última instancia, todo esto afectará su puntaje total en los cursos profesionales. Por tanto, la importancia del capítulo del árbol es evidente.

En general, 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) , en tres Otros algoritmos para implementar árboles binarios basados ​​​​en un algoritmo transversal básico, el concepto de árboles binarios con pistas, algoritmos con pistas y algoritmos de búsqueda con pistas, el concepto, composición y aplicación de árboles binarios óptimos, el concepto y la forma de almacenamiento de los árboles, el relación entre árboles y bosques Algoritmos de recorrido y su conexión con algoritmos de recorrido de árboles binarios, conversión de árboles a bosques y árboles binarios.

Echemos un vistazo a los principales métodos de prueba para 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 incluyen: Examinar directamente la definición de un árbol binario, lo que le permite explicar la diferencia entre un árbol binario y un árbol ordinario de dos ramas; examinar las propiedades de un árbol binario completo y un árbol binario completo, y las cinco propiedades; de un árbol binario ordinario: el número máximo de nodos en el i-ésimo nivel, el número máximo de nodos de un árbol binario con una profundidad de k El número de puntos, la propiedad de n0=n2 1, la profundidad de un completo Árbol binario con n nodos, la relación de conversión entre el nodo secundario y el nodo principal cuando el árbol binario se almacena secuencialmente (izquierda: 2*i, derecha: 2*i 1).

Las respectivas ventajas, desventajas y ocasiones aplicables del almacenamiento secuencial de árboles binarios y el almacenamiento de listas enlazadas binarias, y el método de 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 si el algoritmo en el capítulo del árbol se puede entender y luego se relacionará con el árbol. Capítulo. Si el problema de diseño del algoritmo se puede completar con éxito. Hay tres algoritmos de recorrido de árbol binario: preorden, inorden y postorden. La base para su división depende del orden de acceso a los datos del nodo raíz en cada algoritmo. No solo debe dominar los tres algoritmos recursivos de recorrido y comprender los pasos reales de su ejecución, sino que también debe dominar los tres algoritmos de recorrido no recursivos. Dado que muchos de los algoritmos del capítulo sobre árboles binarios se pueden transformar directamente a partir de los tres algoritmos recursivos (por ejemplo: encontrar el número de hojas), después de dominar los tres algoritmos no recursivos para el recorrido, podrá abordar problemas como como: "Uso de algoritmos no recursivos para encontrar árboles binarios" "El número de hojas" es un tema que siento que tengo mucha energía para escribir. Proporcionaré versiones de memorización de los tres algoritmos recursivos y no recursivos para recorrido en otra serie de artículos (), así que asegúrese de memorizarlos para entonces.

3. Otros algoritmos de árbol binario que se pueden modificar en función de los tres algoritmos transversales:

Encuentre el número de hojas, encuentre el número total de nodos del árbol binario, encuentre el grado de 1 o el grado de El número total de nodos es 2, copie el árbol binario, construya el árbol binario, intercambie los subárboles izquierdo y derecho, busque un nodo específico con un valor de n, elimine un nodo específico con un valor de n, etcétera. Si puede dominar los algoritmos transversales recursivos y no recursivos de los árboles binarios, entonces resolver los problemas anteriores será 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 es relativamente fácil de entender en la forma, consume muchos recursos de memoria. Si hay demasiados niveles de recursividad, inevitablemente provocará el peligro de agotamiento de los recursos. , el árbol binario de pistas apareció de manera grandiosa. Para los árboles binarios con pistas, debe dominar: la esencia de las pistas, tres algoritmos de pistas, el algoritmo transversal de los árboles binarios después de las pistas y otros problemas algorítmicos de los árboles binarios con pistas básicos (como: encontrar el predecesor o el predecesor de un nodo específico en un cierto tipo de árbol binario con pistas) El nodo sucesor es un tipo de pregunta frecuente).

5. Árbol binario óptimo (árbol de Huffman):

El árbol binario óptimo es una estructura de árbol binario especial introducida para resolver problemas específicos. Su premisa es dar cada borde del binario. árbol Dados los pesos, el árbol binario formado de esta manera tiene la suma más pequeña según los pesos. En la sección Árbol binario óptimo, pocas personas examinan directamente el código fuente del algoritmo. Por lo general, se les proporciona un conjunto de datos y se les pide que construyan un árbol binario óptimo basado en este conjunto de datos y encuentren la suma de sus pesos mínimos. El tipo de pregunta no es difícil. Es una subpregunta.

6. Árboles y bosques:

Los árboles binarios son un tipo especial de árbol. Esta especialidad no se debe sólo a que sus ramas tengan como máximo 2 y otras características, sino que También la característica especial más importante es: ¡el árbol binario está ordenado! Es decir: los hijos izquierdo y derecho de un árbol binario no son intercambiables. Si se intercambian, se convertirán en otro árbol binario. De esta manera, pensamos que el árbol binario después del intercambio y el árbol binario original son dos binarios diferentes. árboles. Sin embargo, para los árboles ordinarios de dos ramas, esta propiedad no existe.

El recorrido de árboles y bosques no es tan rico como el de los árboles binarios. Tienen solo dos algoritmos de recorrido: raíz primero y raíz posterior (para los bosques, se denominan: preorden y post). -recorrido de orden).

En los exámenes más difíciles, también hay aquellos que se basan en estos dos algoritmos y luego los amplían para requerir que utilices estos dos algoritmos para diseñar otros algoritmos. Sin embargo, este tipo de método de examen rara vez está disponible en las universidades comunes. , solo requiere que use estos dos algoritmos para diseñar otros algoritmos. Las raíces o las raíces posteriores escriben su secuencia transversal. Los dos recorridos de raíz primera y última raíz corresponden a los algoritmos de recorrido en árboles binarios: el recorrido de raíz primero corresponde al recorrido de preorden de un árbol binario, y el recorrido de raíz posterior corresponde al recorrido en orden de un árbol binario. Esto se ha convertido en un punto de prueba en muchas escuelas y los métodos de prueba varían. Algunos prueban directamente esta oración y otros le piden que resuelva la secuencia transversal primero y luego responda esta pregunta. La razón por la que los árboles binarios, los árboles y los bosques pueden tener las relaciones correspondientes anteriores es todo gracias a la lista binaria enlazada. Un árbol binario usa una lista binaria vinculada para almacenar sus hijos izquierdo y derecho respectivamente. El árbol usa una lista binaria vinculada para almacenar sus hijos y hermanos (llamada lista vinculada hija y hermano), mientras que el bosque también usa una lista binaria vinculada para. almacenar a sus hijos y hermanos.

Cada parte del árbol es un punto clave y cada paso es una pregunta de prueba. Todos deben aprobar cada prueba.

Imagen del Capítulo 6

Si la transición de la investigación de estructura lineal a estructura de árbol es una sublimación de la organización de datos desde la investigación en la disciplina de estructura de datos, entonces de la estructura de árbol La investigación pasó a la investigación de la estructura gráfica, que nos permitió ver el importante papel de la estructura de datos en la resolución de problemas prácticos.

Las características de este capítulo de gráficas son: hay muchos conceptos, estrechamente relacionados con el concepto de gráficas en matemáticas discretas, el algoritmo es complejo, es fácil de probar y es fácil de preguntar. Grandes preguntas, especialmente en escuelas prestigiosas, como curso de examen de ingreso de posgrado, es casi inimaginable sin examinar el conocimiento en los dos capítulos de árboles e imágenes.

Echemos un vistazo a los principales puntos de prueba en este capítulo de gráficos y los métodos de prueba para estos puntos de prueba:

1. Pruebe preguntas conceptuales básicas sobre gráficos:

Estos conceptos son la base para estudiar el capítulo de gráficos. Los conceptos de este capítulo incluyen: la definición y las características de gráficos, gráficos no dirigidos, gráficos dirigidos, gráficos de entrada y salida, gráficos completos, subgrafos generados, longitudes de camino. , bucles, gráficos (fuertemente) conectados, componentes (fuertemente) conectados y otros conceptos. También se deben dominar los problemas de cálculo relacionados asociados con estos conceptos.

2. Examine varias formas de almacenamiento de gráficos:

Las formas de almacenamiento de gráficos incluyen: matriz de adyacencia, lista de adyacencia (inversa), lista de enlaces cruzados 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 a mano otra forma de almacenamiento del gráfico correspondiente a la estructura dada.

3. Examine dos algoritmos de recorrido para gráficos: recorrido en profundidad y recorrido en amplitud.

El recorrido en profundidad y recorrido en amplitud son los dos algoritmos de recorrido básicos para gráficos. Estos dos algoritmos son muy importantes para los gráficos. La importancia de un capítulo es equivalente a la importancia del "recorrido de preorden, orden y postorden" de un capítulo sobre árboles binarios. Durante el examen, las preguntas de diseño de algoritmos en la Figura 1 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 corto y más largo" y "Determinar si existe un camino simple de longitud K entre dos vértices" " Problema", se utilizan los algoritmos de recorrido de amplitud y recorrido de profundidad 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, es necesario escribir el proceso de construcción y el árbol de expansión mínimo generado final en función de las ideas del algoritmo de estos. dos árboles de expansión mínimos.

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 "ordenamiento topológico inverso".

6. Problema de ruta crítica:

Este problema es un problema difícil en la Figura 1. Hay tres claves 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 encuentra mediante el método "de adelante hacia atrás", mientras que la hora más reciente se encuentra mediante el método "de atrás hacia adelante". Si desea encontrar la hora más reciente, debe estar en la hora más temprana de all Sólo se puede hacer después de que se haya pedido todo.

Esta pregunta rara vez se utiliza para probar directamente el código fuente del algoritmo. Generalmente, es necesario describir el proceso de solución y los pasos de acuerdo con el algoritmo en el libro.

Al diseñar el algoritmo de ruta crítica, también debe 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 la hora más temprana y la más reciente. es decir: al comienzo del algoritmo, primero debe establecer 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. El problema del camino más corto:

Junto con el problema del camino crítico, se denominan los dos obstáculos en la Figura 1. La comprensión conceptual es relativamente fácil, la clave es la comprensión de los algoritmos. 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 otro 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 prácticas. Un ejemplo típico es la selección de atracciones turísticas y rutas de viaje. El algoritmo DIJSKTRA se utiliza para resolver el primer problema y el algoritmo FLOYD para resolver el segundo problema. Presta atención a la distinción.

Capítulo 7 Búsqueda

En muchos libros de texto sobre estructuras de datos, la búsqueda y la clasificación se incluyen en estructuras de datos avanzadas. Cabe decir que los dos capítulos de búsqueda y clasificación son la aplicación integral del conocimiento que hemos aprendido anteriormente. Se utilizan árboles, listas vinculadas y otros conocimientos. La aplicación de un determinado aspecto 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 texto en documentos hasta grandes búsquedas en INTERNET. La búsqueda ocupa la mayor parte de nuestro espacio en línea. de la época.

Al revisar el conocimiento de este capítulo, primero debe aclarar los siguientes conceptos:

El significado de las palabras clave, las palabras clave primarias y las palabras clave secundarias. El significado de la búsqueda estática y la búsqueda dinámica; y la diferencia de búsqueda debe recordarse el concepto de longitud de búsqueda promedio ASL y los métodos de cálculo y los resultados de cálculo en varios algoritmos de búsqueda, especialmente los valores de ASL de algunas estructuras típicas.

En el libro de texto de DS, la búsqueda generalmente se divide en tres categorías: primero, búsqueda en la tabla de secuencia; segundo, búsqueda en la tabla de árbol; tercero, búsqueda en la tabla 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 ordenadas utilizamos el método de búsqueda binaria. Para la tercera estructura de índice, utilizamos el 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, la búsqueda binaria requiere especial atención a las 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. Dado que el contenido presentado en esta sección es una búsqueda utilizando una tabla de árbol, es fácil confundirse con algunos conceptos de árbol. El contenido de esta sección está relacionado con el contenido del capítulo del árbol, pero también hay muchas diferencias a las que se debe prestar atención. 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 ellas, las dos primeras estructuras son particularmente importantes y algunas escuelas prestigiosas prefieren realizar el examen B-tree. Dado 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. Si ha aprendido sobre los árboles binarios en el primer capítulo, no será difícil aquí.

El árbol de clasificación binaria, en resumen, es "pequeño a la izquierda y grande a la derecha", 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. Sin embargo, el árbol binario equilibrado tiene limitaciones en la profundidad de los subárboles izquierdo y derecho: el valor absoluto de la diferencia en profundidad debe ser. no ser mayor que 1. Para los árboles de clasificación binaria, a menudo se considera que el algoritmo "determina si un árbol binario es un árbol de clasificación binaria" puede ser 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 que debe dominar los cuatro algoritmos de ajuste de los árboles binarios equilibrados. Una referencia para el ajuste es: en. -Los resultados del recorrido de orden antes y después del ajuste son los mismos.

El árbol B es una mejora adicional del árbol de clasificación binario. El árbol B también puede entenderse como un árbol de clasificación de tres bifurcaciones, cuatro bifurcaciones. 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, es un punto difícil. Los árboles B son uno de los enfoques a los que deben prestar atención los estudiantes que solicitan ingreso a escuelas prestigiosas.

El árbol de claves también se denomina árbol de caracteres y es especialmente adecuado para buscar palabras en inglés. Generalmente, no es necesario describir completamente el código fuente del algoritmo, sino principalmente 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, traducida 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 actuales a buscar, utilizando las palabras clave registradas como variables independientes, diseñe una función después de que la función convierta las palabras clave, el resultado de la interpretación es la dirección. 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 DS. Las preguntas del examen basadas en este capítulo pueden ser de varios tipos: completar los espacios en blanco, elegir. juicio Incluso grandes problemas de algoritmos. Sin embargo, todo se reduce a un punto, que es probar si tiene una comprensión profunda de los diversos algoritmos de clasificación y sus ideas en los libros, así como sus ventajas y desventajas y sus indicadores de rendimiento (complejidad del tiempo).

En este capítulo, nuestro enfoque será diferente al de los capítulos anteriores. Haremos diferentes arreglos para 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.

Desde la perspectiva de los tipos de algoritmos de clasificación, este capítulo explica 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, media inserción, inserción bidireccional y clasificación Hill. La diferencia más fundamental entre estos algoritmos de ordenación por inserción es, en última instancia, qué reglas se utilizan para encontrar el punto de inserción de nuevos elementos. La inserción directa significa buscar en secuencia y la media inserción significa buscar por la mitad. La clasificación en colina tiene como objetivo lograr el propósito de mejorar la eficiencia de la clasificación controlando el incremento del rango total de números que participan en la clasificación "de pequeño a grande" cada vez.

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 una oración: use el número del medio para dividir el grupo de datos que se va a clasificar en dos. La clasificación rápida es algo opuesta a Hill en términos del concepto de "escala del problema" a procesar. La clasificación rápida primero procesa una escala mayor, luego reduce gradualmente la escala de procesamiento y finalmente logra 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 de pila. La diferencia entre estos tres métodos son las reglas según las cuales se selecciona 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 dos números, eliminar continuamente 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 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 la eliminación y el ajuste de 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 grandes problemas de algoritmos en algunas escuelas.

La clasificación por fusión, como sugiere el nombre, es el propósito de ordenar mediante la operación de "fusión". Dado que es una fusión, deben ser dos o más conjuntos de datos para lograr la fusión. Por lo tanto, en la clasificación por combinación, lo que más preocupa es la combinación bidireccional. La idea del algoritmo es relativamente simple, pero se debe tener en cuenta una cosa: la clasificación por fusión es una clasificación estable.

La clasificación por base es un método de clasificación muy especial Precisamente por su carácter especial, 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 Radix 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 se siga la idea de clasificación por bases. no es necesario comparar palabras clave. La secuencia final obtenida de esta manera es una secuencia ordenada.

Se deben dominar las ideas y la implementación de pseudocódigo de varios algoritmos de clasificación en este capítulo, así como su complejidad temporal, al estudiar, preste más atención a la inclusión, el resumen y la comparación. Además, es necesario memorizar y memorizar la Sección 10.7 del libro de texto sobre la base de la comprensión. Esta sección casi se ha convertido en un punto de prueba obligatorio en muchas escuelas cada año.

En este punto, hemos incluido los temas clave en todos los capítulos de estructura de datos. Los estudiantes que usan el libro de texto de Tsinghua Yan pueden consultar los puntos clave que se dan en esta publicación mientras lo revisan. Sin embargo, debido al nivel limitado del autor, es posible que haya muchos puntos de prueba que no se hayan incluido, o que algunos puntos de prueba se hayan incluido incorrectamente. Aquí, el autor espera sinceramente que todos los amigos expresen sus inquietudes directamente y continuaré. para mejorar y publicar nuevas revisiones de la estructura de datos. Resumen y notas

Notas 2 de Yan Weimin centradas en la estructura de datos

Capítulo 2: Tablas lineales (incluidos ejercicios, respuestas y puntos clave)

p>

--- ------------------------------------------ -------- --------------------------

El objetivo de este capítulo es dominar varios Implementaciones básicas en listas de secuencias y listas enlazadas individualmente. Algoritmos 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 efectivos para resolver problemas de aplicación relacionados con tablas lineales.

Se requiere cumplir con los requisitos de lt; memorización y gt; el contenido del nivel incluye: las características estructurales lógicas de las tablas lineales y el uso de operaciones básicas para construir; operaciones más complejas.

Se requiere lograr un contenido integral a nivel de aplicación: el significado y las características de las tablas de secuencia, operaciones de inserción y eliminación en tablas de secuencia y su análisis de rendimiento de tiempo promedio, para resolver problemas de aplicación simples.

Cómo las listas enlazadas representan la relación lógica entre los elementos de una lista lineal; las diferencias en los métodos de enlace de listas enlazadas individualmente, listas enlazadas doblemente y listas enlazadas circulares como creación de tablas, búsqueda e inserción; y eliminación implementada en listas enlazadas individualmente y su complejidad temporal. El papel del puntero de cola en una lista enlazada circular en lugar del puntero de cabeza, así como 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. Utilice algoritmos de diseño de listas vinculadas para resolver problemas de aplicaciones simples.

Se requiere lograr lt; comprender gt; El contenido del nivel es la comparación de listas de secuencias y listas vinculadas, y cómo elegir una como estructura de almacenamiento para lograr un mejor rendimiento espaciotemporal.

------------------------------------------- ----- -------------------------------------

Lógico características estructurales de las tablas lineales Es muy fácil de entender. Como su nombre indica, su estructura lógica es como una línea con nudos. Si hay nudos en esta línea, entonces es una tabla no vacía. y solo puede tener Un nodo inicial tiene y solo puede tener un nodo terminal, y otros nodos solo pueden ser adyacentes a un nodo (predecesor directo y sucesor directo).

Acerca de 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, eliminar, etc.

------------------------------------------- ----- -------------------------------------

El Estructura lógica y suma de tablas lineales. Relaciones entre estructuras de almacenamiento. En una computadora, hay muchas formas de almacenar los nodos de una tabla lineal en una unidad de almacenamiento. El método más sencillo es almacenarlos en orden. Es decir, se almacenan en un grupo de unidades de almacenamiento con direcciones consecutivas en orden según la estructura lógica de la tabla lineal. La ubicación física de cada elemento en la unidad de almacenamiento y la relación adyacente de cada nodo en la estructura lógica son consistentes.

Las operaciones básicas implementadas en la tabla de secuencia analizan principalmente dos operaciones: inserción y eliminación. Dominamos los algoritmos relevantes a través de la práctica. Para las operaciones de inserción y eliminación de la tabla de secuencia, la complejidad temporal promedio es O (n).

------------------------------------------- ----- -------------------------------------

Enlazado Almacenamiento de estructura de mesas lineales. Es diferente de la lista secuencial. La lista vinculada utiliza un conjunto de unidades de almacenamiento arbitrarias para almacenar los nodos de la lista lineal. Este conjunto de unidades de almacenamiento se puede distribuir en cualquier ubicación de la memoria. Por lo tanto, el orden lógico y el orden físico de los nodos en la lista vinculada no son necesariamente los mismos. Por lo tanto, para representar correctamente la relación lógica entre nodos, mientras se almacena el valor de cada nodo, también se almacena la información de dirección de sus nodos sucesores (es decir,