컴퓨터는 컴퓨터 연구 정보로 표현하고 처리하는 과학이다. 여기에는 두 가지 문제, 즉 정보 표상과 정보 처리가 관련되어 있다. 정보는 정보 처리의 알고리즘과 효율성과 직접적인 관련이 있음을 나타냅니다. 정보 (데이터) 사이에는 종종 중요한 구조적 관계가 있습니다. 데이터 구조는 데이터 표현과 데이터 표현의 작업 또는 기능을 캡슐화하는 것으로 논리적 구조와 스토리지 구조의 두 계층으로 나뉩니다.
논리적 구조는 데이터 간의 논리적 구조 관계를 정의합니다. 데이터 요소 간의 관계를 구조라고 하며 집합, 선형 구조, 트리 구조 및 그래픽 구조 (네트워크 구조) 의 네 가지 기본 구조가 있습니다. 트리 구조와 그래픽 구조를 모두 비선형 구조라고 합니다. 컬렉션 구조의 데이터 요소는 같은 유형에 속한다는 점을 제외하고는 다른 관계가 없습니다. 선형 구조에서 요소 간의 일대일 관계, 트리 구조에서 요소 간의 일대다 관계, 그래픽 구조에서 요소 간의 다대다 관계입니다. 도면 구조에서 각 노드의 이전 노드와 후속 노드 수는 임의의 배수일 수 있습니다.
저장 구조는 컴퓨터의 실제 데이터 저장 구조를 정의하며, 순차 저장 구조 및 체인 저장 구조를 포함하여 컴퓨터에서 논리적 구조의 구체적인 구현입니다. 순차 저장법: 논리적으로 인접한 노드를 물리적으로 인접한 스토리지 장치에 저장합니다. 노드 간의 논리적 관계는 스토리지 단위의 인접 관계에 의해 반영되므로 결과 스토리지 표현을 순차 스토리지 구조라고 합니다. 순차 저장 구조는 프로그래밍 언어에서 일반적으로 배열을 통해 구현되는 기본적인 저장 표현 방법입니다. 링크 저장 방법: 논리적으로 인접한 노드가 물리적으로 인접해 있을 필요는 없으며 노드 간의 논리적 관계는 추가 포인터 필드로 표시됩니다. 결과 저장 표현은 체인 저장 구조라고 하며 프로그래밍 언어에서 일반적으로 포인터 유형을 통해 구현됩니다. 인덱스 저장 방법: 스토리지 노드 정보 외에 노드의 주소를 식별하는 추가 인덱스 테이블이 설정됩니다. 해시 저장 방법: 노드의 키워드에 따라 노드의 저장 주소를 직접 계산합니다.
지리 정보 시스템의 개발 및 구현에서는 많은 데이터 구조가 공간 색인, 공간 데이터 저장소, 지도 관리, 지도 기호화 및 렌더링, 공간 분석 등에 사용됩니다. 다음은 간단히 소개해 드리며 참고용으로만 제공됩니다. 독자는 서로 다른 실현을 가질 수 있고, 효율에는 약간의 차이가 있을 수 있다.
배열 또는 체인리스트는 GIS 에서 가장 널리 사용되며 거의 모든 곳에서 볼 수 있습니다. 예를 들어 선 또는 다각형은 점 유형 배열입니다. 쉐이프 파일 파일을 읽을 때 파일은 요소에 포함된 점 수를 기록하고 배열 길이를 결정합니다. 노드를 추가하는 경우 패키지화된 동적 배열 또는 연결된 목록을 사용하여 저장하는 것이 좋습니다. 2 차원 배열로 표현된 그리드 인덱스, 각 배열 요소는 공간 데이터 검색을 용이하게 하기 위해 그리드 범위에 해당하는 데이터 저장소 주소를 기록합니다. 도면층 관리: 지도는 배열 또는 연결된 테이블로 저장된 여러 개의 레이어로 구성되며, 도면층 순서의 조정은 배열 또는 연결된 테이블의 삭제 및 삽입으로 변환됩니다.
스택 및 대기열도 선형 구조이지만 배열 및 연결된 목록보다 더 많은 제한이 있습니다. 스택은 FIFO 이고 대기열은 FIFO 입니다. 예를 들어, 선형 쿼드 트리 인덱스는 중간 순서 트래버스 방법으로 선형화되며, 여기서 트리의 중간 순서 트래버스 및 비반복 알고리즘에는 스택이 필요합니다. GPS 트랙 추적, GPS 포인트 수가 증가함에 따라 트랙이 길어집니다. 실시간 추적 중에 가장 최근 기간의 현재 점만 저장하면 될 수 있습니다. 이전 점은 데이터베이스에 저장되고 그려지지 않습니다. 따라서 순환 대기열을 사용하여 현재 GPS 지점을 저장합니다. 이는 GPS 시계열의 선입 선출 기능을 활용하고 대기열을 재활용할 수 있습니다. 클라이언트의 사진 타일 캐시 풀도 순환 대기열을 사용하여 현재 가시 범위 내에서 얻은 새 타일을 대기열에 삽입할 수 있습니다. 대기열이 가득 차면 대기열에 저장된 가장 오래된 슬라이스가 지워지고 대기열 캐시 풀의 용량이 유지됩니다.
우선 순위 큐는 FIFO 큐와 다른 또 다른 큐입니다. 매번 대기열에서 우선 순위가 가장 높은 요소를 꺼냅니다. 이진 힙은 우선 순위 큐로 최대 힙과 최소 힙으로 나뉩니다. 컬렉션에서 가장 큰 (가장 작은) 요소를 빠르게 찾을 수 있습니다. 최적의 경로, 알고리즘에서 자주 수행하는 단계는 후속 노드에서 최적의 노드를 찾는 것입니다. 최소 힙을 사용하면 현재 노드 가중치가 가장 낮은 노드를 신속하게 찾을 수 있습니다.
트리는 일대다 관계를 갖는 재귀적으로 정의된 데이터 구조입니다. 나무는 루프가 없는 연결도이다. Quadtree 색인은 전형적인 트리 구조입니다. MBR (최소 외부 직사각형) 의 교차 조건에 따라 루트에서 시작하여 레이어별로 아래로 검색하여 요소의 하위 세트를 필터링합니다. XML 구문 분석은 OGC 에서 XML(GML) 구조 자체가 트리 구조입니다. 윤곽, 중첩 관계의 표현은 트리 구조입니다. 속성 데이터 사전 라이브러리, Trie 데이터 구조 및 다중 트리 형식, 속성 사전 라이브러리 구축, 문자열 일치를 통한 속성 조회.
그림은 데이터 요소 간에 다대다 관계가 있는 데이터 구조로, 일반적으로 인접 행렬 또는 인접 테이블로 저장됩니다. 네트워크 또는 관망의 토폴로지 구축은 최적의 경로, 최대 흐름 및 최소 절단 경로, 파이프 폭발, 여행자 등의 네트워크 분석을 용이하게 하는 노드 및 호의 토폴로지 관계를 그림으로 설명하는 네트워크 구조입니다.
Hash, Hash 함수를 설계하여 키 대신 주소를 계산하고 값을 저장합니다. 해시 검색은 효율적이지만 충돌이 발생할 수 있으며 메모리 공간을 많이 차지합니다. 네트워크 또는 관망 구축은 노드의 node_id 를 키로 하고 후속 노드 집합은 값입니다. 을 눌러 섹션을 인쇄할 수도 있습니다 레이어 번호를 키로 사용하는 GML 엔진은 해당 레이어에 속하는 요소 세트를 값으로 사용합니다. 을 눌러 섹션을 인쇄할 수도 있습니다 선 치수, 와이어 절단 후 균일한 키로 접합, 서로 다른 절단 세그먼트의 집합이 값입니다.
GIS 가 일반적으로 사용하는 데이터 구조에 대해 간략하게 설명하지만, 그 이상의 응용이 있습니다. 데이터 구조+알고리즘 = 프로그램 데이터 표현 및 처리에서 데이터 요소 간의 논리적 관계를 분석하고, 논리적 구조를 결정하고, 어떤 스토리지 구조를 구현할 것인지 고려하고, 실제 상황에 따라 분석해야 합니다. 데이터 구조는 알고리즘의 구체적인 구현과 효율성과 직접적인 관련이 있으며 GIS 개발 및 구현에 널리 사용되고 있습니다.
따라서 GIS 는 GIS 의 요구를 기반으로 해야 하는 데이터 구조에 대한 특정 요구 사항을 가지고 있습니다.