Aplicación de la estructura de datos en un sistema de información geográfica.
La informática es una ciencia que utiliza las computadoras para estudiar la representación y el procesamiento de la información. Aquí están involucrados dos temas: la representación de la información y el procesamiento de la información. La representación de la información está directamente relacionada con el algoritmo y la eficiencia del procesamiento de la información. A menudo existen relaciones estructurales importantes entre la información (datos). La estructura de datos es una encapsulación de la representación de datos y las operaciones o funciones en ellos, y se divide en dos niveles: estructura lógica y estructura de almacenamiento.
La estructura lógica define la relación estructural lógica entre datos. La relación entre elementos de datos se llama estructura y hay cuatro estructuras básicas: conjunto, estructura lineal, estructura de árbol y estructura de gráfico (estructura de red). Tanto las estructuras de árbol como las de gráficos se denominan estructuras no lineales. Los elementos de datos en una estructura de colección no tienen otra relación excepto que son del mismo tipo. Existe una relación de uno a uno entre elementos en una estructura lineal, una relación de uno a muchos entre elementos en una estructura de árbol y una relación de muchos a muchos entre elementos en una estructura gráfica. En una estructura gráfica, el número de predecesores y sucesores de cada nodo puede ser múltiplo.
La estructura de almacenamiento define la estructura de almacenamiento real de los datos en la computadora. Es la implementación específica de una determinada estructura lógica en la computadora, incluida la estructura de almacenamiento secuencial y la estructura de almacenamiento en cadena. Método de almacenamiento secuencial: los nodos lógicamente adyacentes se almacenan en unidades de almacenamiento físicamente adyacentes. La relación lógica entre los nodos se refleja en la relación de adyacentes de las unidades de almacenamiento. La representación de almacenamiento resultante se denomina estructura de almacenamiento secuencial. La estructura de almacenamiento secuencial es un método básico de representación de almacenamiento, que generalmente se implementa mediante matrices en lenguajes de programación. Método de almacenamiento vinculado: no es necesario que los nodos lógicamente adyacentes sean físicamente adyacentes, y la relación lógica entre los nodos está representada por campos de puntero adicionales. La representación de almacenamiento resultante se denomina estructura de almacenamiento encadenado y generalmente se implementa en lenguajes de programación mediante tipos de puntero. Método de almacenamiento de índice: además de almacenar información del nodo, también se establece una tabla de índice adicional para identificar la dirección del nodo. Método de almacenamiento hash: calcule directamente la dirección de almacenamiento del nodo en función de la palabra clave del nodo.
En el desarrollo e implementación de sistemas de información geográfica, se utilizarán muchas estructuras de datos para indexación espacial, almacenamiento de datos espaciales, gestión de mapas, simbolización y representación de mapas, análisis espacial, etc. La siguiente es una breve introducción solo como referencia. Los lectores pueden tener diferentes implementaciones y habrá algunas diferencias en la eficiencia.
Los arrays o listas enlazadas son los más utilizados en SIG y se pueden encontrar en casi todas partes. Por ejemplo, una línea o un polígono son matrices de tipo punto. Cuando se lee el archivo de forma, el archivo registra el número de puntos contenidos en los elementos y determina la longitud de la matriz. Si agrega nodos, es mejor utilizar matrices dinámicas empaquetadas o listas vinculadas para el almacenamiento. Índice de cuadrícula, representado por una matriz bidimensional, cada elemento de la matriz registra la dirección de almacenamiento de datos correspondiente al rango de la cuadrícula, lo que facilita la recuperación de capas de datos espaciales, un mapa se compone de varias capas superpuestas y la información de estas capas es; Se almacena en forma de matriz o lista vinculada, y el ajuste del orden de las capas se transforma en eliminación e inserción de matriz o lista vinculada.
Las pilas y colas también son estructuras lineales, pero tienen más restricciones que las matrices y las listas enlazadas. La pila es FIFO y la cola es FIFO. Por ejemplo, el índice lineal de cuatro árboles se linealiza utilizando el método de recorrido en orden, en el que el recorrido en orden y el algoritmo no recursivo del árbol requieren el uso de una pila de seguimiento de trayectoria GPS, a medida que aumenta el número de puntos GPS; , la trayectoria será cada vez más larga. En el proceso de seguimiento en tiempo real, es posible que solo necesite guardar el punto actual en el último período, y los puntos anteriores se guardarán en la base de datos y no se extraerán. Por lo tanto, se utiliza una cola circular para almacenar algunos puntos GPS actuales, lo que aprovecha la naturaleza de primero en entrar, primero en salir de la serie temporal de GPS y permite reciclar la cola. El grupo de caché de mosaicos de imágenes del cliente también puede usar una cola circular para insertar en la cola nuevos mosaicos obtenidos dentro del rango visible actual. Cuando la cola está llena, los mosaicos más antiguos almacenados en la cola se borran mientras se mantiene la capacidad del grupo de búfer de la cola.
La cola prioritaria es otro tipo de cola diferente a la cola FIFO. El elemento de mayor prioridad se toma de la cola cada vez. El montón binario es una cola de prioridad y se divide en un montón máximo y un montón mínimo. Puede encontrar rápidamente el elemento más grande (más pequeño) de un conjunto. Ruta óptima, un paso que se realiza a menudo en el algoritmo es encontrar el nodo óptimo a partir de los nodos sucesores. Utilizando el montón mínimo, se puede encontrar rápidamente el nodo con el peso más pequeño del nodo actual.
Un árbol es una estructura de datos definida recursivamente con una relación de uno a muchos. Un árbol es un gráfico conexo sin bucles. El índice Quadtree es una estructura de árbol típica.
De acuerdo con la condición de intersección de MBR (rectángulo delimitador mínimo), busque hacia abajo capa por capa comenzando desde la raíz y filtre un subconjunto de elementos. En el análisis XML en OGC, la estructura XML (GML) en sí es una estructura de árbol; el esquema, la expresión de relaciones anidadas, es una estructura de árbol. La biblioteca del diccionario de datos de atributos utiliza la estructura de datos Trie y la forma de múltiples árboles para establecer el diccionario de atributos. La biblioteca implementa la consulta de atributos a través de la coincidencia de cadenas.
Un gráfico es una estructura de datos con una relación de muchos a muchos entre elementos de datos, generalmente almacenada con una matriz de adyacencia o una lista de adyacencia. La construcción topológica de una red de carreteras o una red de tuberías es una estructura de red que utiliza gráficos para describir las relaciones topológicas de nodos y arcos, lo que facilita el análisis de la red, como rutas óptimas, flujo máximo y rutas de corte mínimo, explosiones de tuberías y vendedores ambulantes.
Hash, diseña una función hash para sustituir la clave para calcular la dirección y almacenar el valor. La búsqueda de hash es eficiente, pero puede haber conflictos y ocupa mucho espacio en la memoria. La red de carreteras o red de tuberías se construye con el node_id del nodo como clave y el conjunto de nodos posteriores como valor; el motor GML, con el número de capa como clave y el conjunto de elementos que pertenecen a la capa como el valor;; etiquetado de línea, unificado después del corte de línea. El empalme clave, el conjunto de diferentes segmentos de corte es el valor.
Lo anterior presenta brevemente las estructuras de datos SIG comúnmente utilizadas, pero las aplicaciones son mucho más que estas. Estructura de datos + algoritmo = programa. En la representación y el procesamiento de datos, es necesario analizar la relación lógica entre los elementos de datos y determinar la estructura lógica. También es necesario considerar qué estructura de almacenamiento implementar y analizarla en función de la situación real. La estructura de datos está directamente relacionada con la implementación específica y la eficiencia del algoritmo y se usa ampliamente en el desarrollo e implementación de SIG.
Por lo tanto, el SIG tiene requisitos específicos para la estructura de datos, y esta aplicación específica debe basarse en las necesidades del SIG.