중화사전망 - 중국어 사전 - 이 문서에서는 30 가지 중요한 데이터 구조와 알고리즘을 소개합니다.
이 문서에서는 30 가지 중요한 데이터 구조와 알고리즘을 소개합니다.
그들은 무엇을 위해 인가?
극장 한 줄의 의자를 상상해 보세요. 각 의자에는 위치 (왼쪽에서 오른쪽으로) 가 할당되므로 각 관객은 그가 앉을 의자에서 숫자를 할당합니다. 이것은 배열입니다. 전체 극장 (의자 행) 으로 문제를 확장하면 2 차원 배열 (행렬) 이 생깁니다.
특징
체인 테이블은 배열처럼 선형 데이터 구조입니다. 연결된 테이블과 배열의 주요 차이점은 연결된 테이블의 요소가 연속 메모리 위치에 저장되지 않는다는 것입니다. 이는 노드로 구성됩니다. 엔티티는 현재 요소의 값과 다음 요소의 주소 참조를 저장합니다. 이런 식으로 요소는 포인터로 연결됩니다.
그들은 무엇을 위해 인가?
연결된 목록의 관련 응용 프로그램 중 하나는 브라우저의 이전 페이지와 다음 페이지를 구현하는 것입니다. 양방향 체인 테이블은 사용자 표시 페이지를 저장하는 완벽한 데이터 구조입니다.
특징
Stack 은 제한된 액세스 세트의 개념을 형식화하는 추상 데이터 유형입니다. 이 제한은 후입선출 (LIFO) 규칙을 따릅니다. 따라서 스택에 추가된 마지막 요소는 스택에서 제거한 첫 번째 요소입니다.
스택은 배열 또는 연결된 목록을 사용하여 수행할 수 있습니다.
그들은 무엇을 위해 인가?
실생활에서 가장 흔한 예는 식당에서 접시를 접는 것이다. 먼저 지붕을 철거하다. 맨 아래에 놓인 접시는 스택에 가장 오래 남아 있는 접시입니다.
스택의 가장 유용한 상황 중 하나는 주어진 요소의 역순을 얻어야 한다는 것이다. 그것들을 모두 스택 위로 밀고 튀어나온다.
또 다른 흥미로운 응용은 유효한 괄호의 문제이다. 주어진 괄호는 스택을 사용하여 일치하는지 확인할 수 있습니다.
특징
대기열은 앞서 설명한 스택처럼 제한된 액세스 세트의 또 다른 데이터 유형입니다. 주요 차이점은 대기열이 FIFO (선입선출) 모델에 따라 구성된다는 것입니다. 즉, 삽입된 대기열의 첫 번째 요소는 제거된 첫 번째 요소입니다. 고정 길이 배열, 루프 배열 또는 연결된 목록을 사용하여 대기열을 구현할 수 있습니다.
그들은 무엇을 위해 인가?
이 추상 데이터 유형 (ADT) 의 가장 좋은 용도는 물론 실제 대기열을 시뮬레이션하는 것입니다. 예를 들어 콜 센터 응용 프로그램에서 큐는 고객이 컨설턴트의 도움을 기다리도록 하는 데 사용됩니다. 즉, 고객은 그들이 전화하는 순서대로 도움을 받아야 합니다.
특별하고 중요한 대기열 유형은 우선 순위 대기열입니다. 요소는 연관된 "우선 순위" 에 따라 대기열에 삽입됩니다. 우선 순위가 가장 높은 요소가 먼저 대기열에 삽입됩니다. 이 ADT 는 많은 그래픽 알고리즘 (Dijkstra 알고리즘, BFS, Prim 알고리즘, Huffman 인코딩) 에서 필수적입니다. 힙을 사용하여 구현됩니다.
또 다른 특수한 유형의 대기열은 deque 대기열 (pun 이 "deck" 로 읽음) 입니다. 대기열의 양쪽 끝에서 요소를 삽입/삭제할 수 있습니다.
특징
지도 (사전) 는 키 세트와 값 세트가 포함된 추상 데이터 유형입니다. 각 키에는 연관된 값이 있습니다.
해시 테이블은 특별한 유형의 매핑입니다. 해시 함수를 사용하여 해시 코드를 생성하고 배럴 또는 슬롯 배열에 배치합니다. 즉, 키를 해시하고 결과 해시 표시 값이 저장되는 위치입니다.
가장 일반적인 해시 함수 (많은 해시 함수 중) 는 모듈 상수 함수입니다. 예를 들어 상수가 6 이면 키 x 의 값은 x%6 입니다.
해시 함수는 각 키를 고유한 통에 할당하는 것이 이상적이지만 대부분 불완전한 함수를 사용하여 생성된 값이 동일한 키 간에 충돌이 발생할 수 있습니다. 이런 충돌은 항상 어떤 식으로든 적응한다.
그들은 무엇을 위해 인가?
지도의 가장 유명한 응용은 언어 사전이다. 이 언어의 각 단어에는 자체 정의가 있습니다. 이 작업은 정렬된 매핑을 사용하여 수행됩니다 (키는 알파벳순으로 정렬됨).
주소록도 지도입니다. 각 이름에는 전화 번호가 있습니다.
또 다른 유용한 응용은 값의 표준화이다. 하루 중 매 분마다 0 에서 1439 (24 시간 = 1440 분) 사이의 색인을 지정한다고 가정해 봅시다. 해시 함수는 h(x) = x 시간 *60+x 분이 됩니다.
특징
용어:
Maps 는 자체 균형 빨간색 흑나무로 구현되기 때문에 (문장 뒤에서 설명됨) 모든 작업은 O(log n) 에서 수행됩니다. 모든 해시 테이블 작업은 상수입니다.
그림은 한 쌍의 두 집합을 나타내는 비선형 데이터 구조입니다. G={V, E} 여기서 V 는 정점 세트 (노드) 이고 E 는 모서리 세트 (화살표) 입니다. 노드는 두 노드 간의 종속성 (경우에 따라 비용/거리와 관련됨) 을 설명하는 모서리 선으로 상호 연결된 값입니다.
두 가지 주요 유형의 그래프, 즉 직접 그래프와 무 지향성 그래프가 있습니다. 무향 그래프에서 가장자리 (x, y) 는 두 방향 (x, y) 과 (y, x) 모두에서 사용할 수 있습니다. 유향 그래프에서 가장자리 (x, y) 를 화살표라고 하며, 방향은 이름의 정점 순서에 따라 제공됩니다. 화살표 (x, y) 는 화살표 (y, x) 와 다릅니다.
그들은 무엇을 위해 인가?
특징
도론은 넓은 영역이지만, 우리는 가장 유명한 개념에 초점을 맞출 것이다.
나무는 무향 그래프입니다. 이 그래프는 연결이 가장 작습니다. (가장자리를 제거하면 그림이 더 이상 연결되지 않습니다.), 무순환이 가장 큽니다. (가장자리를 추가하면 그림이 더 이상 무환이 아닙니다.) 따라서 무순환 연결 무향도는 모두 나무이지만, 간단히 하기 위해 우리는 이를 뿌리가 있는 나무라고 부른다. (알버트 아인슈타인, Northern Exposure (미국 TV 드라마), 성공명언)
루트는 고정된 노드이며, 트리의 가장자리 방향을 결정하므로 모든 "시작" 이 있는 곳입니다. 잎은 나무의 끝 노드입니다. 이것은 모든 "끝" 이 있는 곳입니다.
정점의 하위 정점은 그 아래 이벤트의 정점입니다. 정점에는 여러 개의 하위 노드가 있을 수 있습니다. 정점의 상위 노드는 그 위에 있는 이벤트 정점입니다. 고유합니다.
그들은 무엇을 위해 인가?
계층을 설명해야 할 때마다 트리를 사용합니다. 우리 자신의 계보가 바로 완벽한 예이다. 너의 가장 오래된 조상은 나무뿌리이다. 최연소 세대는 나뭇잎의 집합을 대표한다.
나무는 또한 당신이 일하는 회사의 등급제도를 대표할 수 있다. 이렇게 하면 너는 누가 너의 상급자인지, 네가 누구를 관리해야 하는지 알 수 있다.
특징
이진 트리는 특별한 트리입니다. 각 정점에는 최대 두 개의 하위 노드가 있을 수 있습니다. 엄격한 이진 트리에는 잎을 제외한 각 노드에 두 개의 하위 노드가 있습니다. 완전한 n 계층 이진 트리 모두 2? -1 개의 가능한 노드.
이진 조회 트리는 노드 값이 완전히 정렬된 집합에 속하는 이진 트리입니다. 임의로 선택한 노드의 값은 왼쪽 하위 트리의 모든 값보다 크고 오른쪽 하위 트리의 모든 값보다 작습니다.
그들은 무엇을 위해 인가?
BT 의 중요한 응용 프로그램 중 하나는 논리 표현식의 표현과 평가이다. 각 표현식은 변수/상수 및 연산자로 분해될 수 있습니다. 이 표현식 작성 방법을 역폴란드 표기법 (RPN) 이라고 합니다. 이렇게 하면 내부 노드가 연산자이고 잎은 변수/상수인 다이트리 트리를 형성할 수 있습니다. 이를 추상 구문 트리 (AST) 라고 합니다.
BST 는 주요 속성을 빠르게 검색할 수 있기 때문에 자주 사용됩니다. BST 를 사용하여 AVL 트리, 빨간색 블랙 트리, 순서 세트 및 매핑을 구현합니다.
특징
BST 에는 세 가지 유형의 DFS 트래버스가 있습니다.
이러한 모든 유형의 나무는 자기 균형 이진 검색 방법 트리입니다. 차이점은 로그 시간 동안 높이의 균형을 잡는다는 것입니다.
AVL 트리는 각 삽입/삭제 후 자체 균형을 이룹니다. 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 사이의 최대 모듈러 차이는 1 이기 때문입니다. AVL 은 아델슨 빌스키와 랜디스라는 발명가의 이름을 따서 명명되었습니다.
빨간색-검은색 트리에서 각 노드는 각 삽입/삭제 작업 후 균형을 유지하기 위해 색상을 나타내는 추가 비트를 저장합니다.
Splay 트리에서 최근에 액세스한 노드는 신속하게 다시 액세스할 수 있으므로 모든 작업의 상각 시간 복잡성은 여전히 O(log n) 입니다.
그들은 무엇을 위해 인가?
AVL 은 데이터베이스 이론에서 최고의 데이터 구조인 것 같다.
RBT (red black tree) 는 텍스트 세그먼트나 숫자와 같은 비교 가능한 데이터 세그먼트를 구성하는 데 사용됩니다. Java 버전 8 에서 HashMap 은 RBT 를 사용하여 구현됩니다. 계산 기하학 및 함수 프로그래밍의 데이터 구조도 RBT 를 사용하여 구축됩니다.
Windows NT (가상 메모리, 네트워크 및 파일 시스템 코드) 에서 재생 트리는 캐시, 메모리 할당자, 가비지 수집기, 데이터 압축, rope (긴 텍스트 문자열에 사용되는 문자열 아님) 에 사용됩니다.
특징
최소 힙은 각 노드의 값이 상위 노드의 값보다 크거나 같은 이진 트리입니다. val[par[x]]