Los capítulos de la disciplina 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 de archivos en línea, diseño y asignación de almacenamiento dinámico.
Para la mayoría de las escuelas, los tres capítulos de "salida, archivos y asignación de almacenamiento dinámico" 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 de algoritmos basadas en matrices también son relativamente comunes y la relación de puntuación fluctúa mucho, por lo que son la "unidad opcional" o la "unidad de espera" del 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.
Búsqueda: Capítulos clave 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: similar a encontrar un capítulo, este capítulo es a la vez un capítulo clave y un capítulo 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 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 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 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, binaria con vectores de fila auxiliares y almacenamiento de listas reticuladas. 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 árboles es un salto en los cursos de estudio de estructuras de datos. La finalización de este salto afectará directamente si puede lograr puntajes altos en el examen real y, en última instancia, todo esto afectará el puntaje total del curso profesional. 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.