자바스크립트에는 데이터 구조가 있나요?-프런트엔드 Q&A-php.cn

JavaScript에는 데이터 구조가 있습니다. 데이터 구조는 서로 하나 이상의 특정 관계를 갖는 데이터 요소의 모음을 의미합니다. 데이터 구조는 데이터 객체를 효과적으로 관리하고 컴퓨팅 성능을 향상시킬 수 있습니다. , 대기열, 연결 목록, 사전, 해시, 그래프 및 이진 검색 트리.

자바스크립트에는 데이터 구조가 있나요?

이 튜토리얼의 운영 환경: Windows 10 시스템, JavaScript 버전 1.8.5, Dell G3 컴퓨터.

Javascript에 데이터 구조가 있나요?

Javascript에 데이터 구조가 있습니다

데이터 구조: 목록, 스택, 큐, 연결 목록, 사전, 해시, 그래프 및 이진 검색 트리

List

매일 인생에서 사람들은 할일 목록, 쇼핑 목록, 상위 10개 목록 등 목록을 자주 사용합니다. 컴퓨터 프로그램도 목록을 사용합니다. 선택 목록은 다음 조건에서 데이터 구조로 특히 유용합니다.

데이터 구조가 비교적 간단합니다

긴 순서로 요소를 찾거나 정렬할 필요가 없습니다

그 반대의 경우도 마찬가지입니다. 데이터 구조가 매우 복잡하다면 리스트의 역할은 그다지 크지 않습니다.

Stack

스택은 특별한 종류의 목록입니다. 스택의 요소는 스택의 맨 위라고 불리는 목록의 한쪽 끝을 통해서만 액세스할 수 있습니다. 우리가 식당에서 흔히 볼 수 있는 접시 더미가 현실 세계의 흔한 접시 더미의 예라고 상상해 보세요. 접시는 씻어서 맨 위에만 올려 놓을 수 있습니다. 스택은 후입선출(Last In First Out) 데이터 구조로 알려져 있습니다. 스택의 최상위에서만 데이터를 추가하거나 삭제할 수 있어 이러한 작업이 빠르기 때문에 효율적인 데이터 구조입니다.

사용 조건:

데이터 저장이 후입선출 또는 선입선출 원칙을 충족하는 한 스택 사용이 우선적으로 적용됩니다

Queue

큐도 일종의 목록입니다. 차이점은 큐는 큐 끝에 요소를 삽입하고 시작 부분에만 요소를 삭제할 수 있다는 것입니다. 우리가 은행에 줄을 서 있는데, 맨 앞에 있는 사람들이 가장 먼저 장사를 하고, 뒤에서 오는 사람들은 자신의 차례가 될 때까지 줄 뒤에서 기다려야 한다고 상상해 보십시오.

사용 조건:

데이터 저장소가 선입선출, 후입후출 원칙을 충족하는 한 대기열 사용에 우선순위가 부여됩니다.

일반적인 응용 시나리오:

대기열이 주로 사용됩니다. 시간과 관련된 곳, 특히 운영 체제에서 대기열은 멀티 태스킹을 달성하는 중요한 메커니즘입니다

메시지 메커니즘은 대기열을 통해 구현될 수 있으며 프로세스 스케줄링도 대기열을 사용하여 구현됩니다

Linked list

연결리스트(linked list)도 일종의 목록인데 왜 연결리스트가 필요하고, 자바스크립트에서는 배열이 필요한가? 가장 큰 문제는 객체로 구현된다는 점인데, 이는 다른 언어(예: C++ 등)의 배열에 비해 매우 비효율적이다. 그리고 자바). 실제 사용 시 배열이 느리다면 대신 연결된 목록을 사용해 보세요.

사용 조건:

연결된 목록은 1차원 배열을 사용할 수 있는 거의 모든 상황에서 사용할 수 있습니다. 무작위 액세스가 필요한 경우에도 어레이가 더 나은 선택입니다.

Dictionary

사전은 키-값 쌍으로 데이터를 저장하는 데이터 구조입니다. JavaScript의 Object 클래스는 사전 형태로 설계되었습니다. JavaScript에서는 사전 클래스를 구현하여 이러한 사전형 개체를 보다 쉽게 사용할 수 있습니다. 사전은 개체의 공통 기능을 구현하고 이에 따라 원하는 기능을 확장할 수 있으므로 개체는 JavaScript 작성에서 어디에서나 볼 수 있습니다. 또한 매우 명백합니다.

Hash

해시(해시 테이블이라고도 함)는 일반적으로 사용되는 배열 저장 기술입니다. 해시된 배열을 빠르게 삽입하거나 검색할 수 있습니다. 해싱에 사용되는 데이터 구조를 해시 테이블이라고 합니다. 해시 테이블에 데이터를 삽입, 삭제, 검색하는 작업은 매우 빠르지만 배열에서 최대값과 최소값을 찾는 등의 검색 작업에는 비효율적입니다. 이러한 작업에는 아래 설명된 이진 검색 트리와 같은 다른 데이터 구조를 사용해야 합니다.

해시 테이블은 JavaScript의 배열을 기반으로 설계할 수 있습니다. 배열의 길이는 미리 정해져 있으며, 모든 요소는 해당 요소에 해당하는 키에 따라 배열의 특정 위치에 저장됩니다. 여기서의 키와 객체의 키는 유형의 개념입니다. 해시 테이블을 사용하여 배열을 저장할 때 해시 함수는 키를 0부터 해시 테이블 길이까지의 숫자로 매핑합니다.

효율적인 해시 함수를 사용하더라도 두 개의 키가 동일한 값으로 매핑될 수 있습니다. 이러한 현상을 충돌이라고 합니다. 일반적인 충돌 처리 방법에는 오픈 체인 방법 및 선형 감지 방법이 포함됩니다(특정 개념에 관심이 있는 경우 온라인에서 자신있게 학습할 수 있습니다)

사용 조건:

데이터 삽입, 삭제 및 검색에 사용할 수 있습니다. 데이터 찾기에 적합하지 않습니다

Picture

그래프는 모서리 세트와 꼭지점 세트로 구성됩니다. 지도는 우리 주변에서 흔히 볼 수 있는 실제 장면입니다. 예를 들어 모든 두 마을은 일종의 도로로 연결되어 있습니다. 위의 각 마을은 정점으로 간주될 수 있으며, 마을을 연결하는 도로는 가장자리로 간주될 수 있습니다. 간선은 정점 쌍(v1, v2)으로 정의됩니다. 여기서 v1과 v2는 그래프의 두 정점입니다. 정점에도 가중치가 있어 비용이 됩니다. 그래프의 꼭지점 쌍이 순서대로 정렬된 경우 방향성 그래프(예: 일반 흐름도)라고 하며, 그렇지 않은 경우에는 정렬되지 않은 그래프라고 합니다.

사용 시나리오(그래프를 사용하여 실제 시스템 모델링):

교통 시스템, 정점은 거리 교차로를 나타내는 데 사용할 수 있으며 가장자리는 거리를 나타내는 데 사용할 수 있습니다. 가중치 간선은 속도 제한이나 차선 수를 나타낼 수 있습니다. 이 시스템은 최적의 경로와 혼잡할 가능성이 가장 높은 거리를 결정하는 데 사용될 수 있습니다.

모든 교통 시스템은 다이어그램을 사용하여 모델링할 수 있습니다. 예를 들어, 항공사는 다이어그램을 사용하여 비행 시스템을 모델링할 수 있습니다. 각 공항을 정점으로 간주하고 두 정점을 통과하는 각 경로를 가장자리로 간주합니다. 가중치 간선은 모델링 대상에 따라 한 공항에서 다른 공항으로의 비행 비용 또는 두 공항 사이의 거리를 나타낼 수 있습니다.

그래프 검색에는 깊이 우선 검색과 너비 우선 검색이라는 두 가지 주요 알고리즘이 있습니다.

이진 트리와 이진 검색 트리

트리는 컴퓨터 과학에서 자주 사용되는 데이터 구조입니다. 트리는 계층적 방식으로 데이터를 저장하는 비선형 데이터 구조입니다.

이진 트리의 각 노드는 자식 노드를 2개 이상 가질 수 없습니다. 부모 노드의 두 자식 노드를 각각 왼쪽 노드, 오른쪽 노드라고 합니다. 자식 노드 수를 2개로 제한하면 트리에 데이터를 삽입, 검색, 삭제하는 효율적인 프로그램을 작성할 수 있습니다.

BST(이진 검색 트리)는 상대적으로 작은 값이 왼쪽 노드에 저장되고 큰 값이 오른쪽 노드에 저장되는 특별한 종류의 이진 트리입니다. 이 기능을 사용하면 단어, 문자열 등 숫자 데이터와 숫자가 아닌 데이터 모두에 대해 매우 효율적으로 검색할 수 있습니다.

이진 검색 트리 구현 방법

function Node(data, left, right) { // 创建节点
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show
}
function show () { // 显示树的数据
  return this.data
}
function BST () { // 二叉查找树类
  this.root = null;
  this.insert = insert;
  this.inOrder = inOrder; // inOrder是遍历BST的方式
}
function insert (data) { // 向树中插入数据
  var n = new Node(data, null, null)
  if (this.root == null) {
    this.root = n;
  } else {
    var current = this.root;
    var parent;
    while (true) {
  parent = current
  if (data < current.data) {
current = current.left;
if (current == null) {
  parent.left = n;
  break;
}
  } else {
current = current.right;
if (current == null) {
  parent.right = n;
  break;
}
  }
    }
  }
}

로그인 후 복사

BST를 통과하는 방법에는 세 가지가 있습니다: 순차 탐색(트리의 모든 노드를 오름차순으로 방문하고 먼저 왼쪽 노드를 방문한 다음 루트 노드를 방문하고 마지막으로 오른쪽 노드를 방문) 노드), 선순 순회(루트 노드를 먼저 방문한 후 동일한 방식으로 왼쪽 노드와 오른쪽 노드에 액세스), 후순 순회(리프 노드를 먼저 방문하여 왼쪽 하위 트리에서 오른쪽 하위 트리로 이동한 다음 루트 노드로)

[관련 권장 사항: javascript video Tutorial, web front-end]

위 내용은 자바스크립트에는 데이터 구조가 있나요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!