javascript 구현 데이터 구조: 선형 표 - 간단 한 예시 및 선형 표 의 순서 표시 와 실현
16049 단어 JavaScript
그 중:
선형 표 의 저장 구조
이런 상황 에서 데이터 요 소 를 기록 (record) 이 라 고 부 르 고 대량의 기록 을 가 진 선형 표를 파일 (file) 이 라 고도 부른다.
1. 두 개의 선형 표 LA 와 LB 를 이용 하여 각각 두 개의 집합 A 와 B 를 나타 낸다 고 가정 하면 현재 새로운 집합 A = AUB 를 요구한다. 그러면 선형 표 LA 를 다음 과 같이 조작 해 야 한다. 선형 표 LA 를 확대 하면 선형 표 LB 에 존재 하지 않 고 선형 표 LB 에 존재 할 것 이다.
선형 표 LA 의 데이터 요 소 는 선형 표 LA 에 삽 입 됩 니 다. 선형 표 LB 에서 모든 데이터 요 소 를 순서대로 얻 고 값 에 따라 선형 표 LA 에서 찾 으 면 존재 하지 않 으 면 삽 입 됩 니 다.
다음은 알고리즘 설명 입 니 다.
1 // b a a
2
3 var a = [1, 2, 3, 4, 5];
4 var b = [1, 3, 5, 7, 9];
5
6 function union(a, b) {
7 var elem, equal;
8
9 for (var i = 0, bLen = b.length; i < bLen; i++) {
10 elem = b[i];
11 equal = false;
12
13 for (var j = 0, aLen = a.length; j < aLen; j++) {
14 if (elem === a[j]) {
15 equal = true;
16 break;
17 }
18 }
19
20 if (!equal) a.push(elem);
21 }
22 }
23
24 union(a, b);
25 console.log(a);
26 // [1, 2, 3, 4, 5, 7, 9]
27
28 // ：O(aLen * bLen)2. 이미 알 고 있 는 선형 표 LA 와 LB 의 데이터 요 소 는 값 에 따라 점점 줄 어 들 지 않 고 질서 있 게 배열 되 어 있 습 니 다. 현 재 는 LA 와 LB 를 새로운 선형 표 LC 로 통합 시 키 고 LC 중의 데이터 요 소 는 아직도 값 에 따라 점점 줄 어 들 지 않 고 질서 있 게 배열 해 야 합 니 다.
우 리 는 LA 와 LB 의 색인 을 각각 저장 하고 해당 하 는 요 소 를 비교 할 수 있 는 두 개의 변 수 를 설정 할 수 있 습 니 다.
1 1 // a b
2 2 // a b c，c
3 3 var a = [3, 5, 8, 11];
4 4 var b = [2, 6, 8, 9, 11, 15, 20];
5 5
6 6 function mergeList(a, b) {
7 7 var c = [], aElem, bElem;
8 8 var i = 0, j = 0, k = 0;
9 9 var aLen = a.length;
10 10 var bLen = b.length;
11 11
12 12 while (i < aLen && j < bLen) {
13 13 aElem = a[i];
14 14 bElem = b[j];
15 15
16 16 if (aElem < bElem) {
17 17 c[k++] = aElem;
18 18 i++;
19 19 } else {
20 20 c[k++] = bElem;
21 21 j++;
22 22 }
23 23 }
24 24
25 25 while (i < aLen) {
26 26 c[k++] = a[i++];
27 27 }
28 28
29 29 while (j < bLen) {
30 30 c[k++] = b[j++];
31 31 }
32 32
33 33 return c;
34 34 }
35 35
36 36 var c = mergeList(a, b);
37 37 console.log(c);
38 38 // [2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20]
39 39
40 40 // ： O(aLen + bLen)선형 표 의 순서 표시 와 실현
선형 표 의 순 서 는 한 그룹의 주소 로 연속 적 인 저장 장치 로 선형 표를 한 번 에 저장 하 는 데이터 요 소 를 말한다.
선형 표 의 모든 요 소 는 l 개의 저장 소 를 사용 하고 첫 번 째 셀 의 저장 주 소 를 왼쪽 데이터 요소 의 저장 위치 로 가정 합 니 다. 선형 표 의 i1 번 째 데이터 요소 의 저장 위치 LOC (a (i + 1) 와 i 번 째 요소 의 저장 위치 LOC (a (i) 는 다음 과 같은 관 계 를 만족 시 킵 니 다.
LOC(a(i + 1)) = LOC(a(i)) + l;
선형 표 의 이러한 표 시 는 선형 표 의 순서 저장 구조 나 순서 맵 (sequential mapping) 이 라 고 합 니 다. 일반적으로 이러한 저장 구조의 선형 표를 순서 표 라 고 합 니 다. 표 에 인접 한 요소 a (i) 와 a (i + 1) 에 인접 한 저장 위치 LOC (a (i) 를 부여 하 는 것 이 특징 입 니 다.
LOC (a (i + 1) 와 같 습 니 다. 다시 말 하면 요소 로 컴퓨터 내 '물리 적 위치 인접' 입 니 다.선형 표 에서 데이터 요소 간 의 논리 적 관 계 를 나타 낸다. 모든 데이터 요소 의 저장 위 치 는 선형 표 의 시작 위치 와 1 개 차이 가 나 고 데이터 요소 가 선형 표 에서 의 위치 와 정비례 하 는 상수 이다. 따라서 선형 표 의 시작 위 치 를 확정 하면 선형 표 에서 임 의 데이터 요 소 는 무 작위 로 액세스 할 수 있 기 때문에 선형 표 의 순서 저장 구 조 는 일종 이다.무 작위 액세스 의 저장 구조.
고급 프로 그래 밍 언어 에 있 는 배열 형식 도 무 작위 액세스 특성 이 있 기 때문에 데이터 구조 에 있 는 순서 저장 구 조 를 배열 로 설명 합 니 다.
선형 표 의 순 서 를 더욱 명확 하 게 표시 하기 위해 우 리 는 js 의 위조 배열 을 실현 하여 시 뮬 레이 션 을 하고 요 소 를 삽입 하고 삭제 합 니 다.
1 //
2 var a = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5};
3 a.length = 6;
4
5 function insert(a, i, elem) {
6 if (!elem) return;
7
8 var len = a.length;
9 if (i >= len) {
10 while (len < i) {
11 a[len++] = undefined;
12 a.length++;
13 }
14 a[i] = elem;
15 } else {
16 while (len > i) {
17 a[len--] = a[len];
18 }
19 a[i] = elem;
20 }
21 a.length++;
22 }
23
24 insert(a, 3, 8);
25 insert(a, 10, 10);
26 console.log(a);
27
28 //
29
30 function del(a, i) {
31 var temp = a[i];
32 var j = i + 1;
33 var len = a.length;
34
35 while (j < len) {
36 a[j - 1] = a[j++];
37 }
38 a.length--;
39 delete a[len - 1];
40
41 return temp;
42 }
43
44 del(a, 3);
45 console.log(a);
46 del(a, 10);
47 console.log(a);
48
49 // ： O(a.length)선형 표 의 순서 저장 구조의 특징 은 논리 적 관계 에서 인접 한 두 요소 가 물리 적 위치 에서 도 인접 하기 때문에 랜 덤 액세스 표 의 모든 요 소 를 사용 할 수 있다 는 것 이다. 그 저장 위 치 는 간단 하고 직관 적 인 공식 으로 표시 할 수 있다. 그 다음 에 다른 한편, 이 특징 은 이러한 저장 구조의 약점 을 초래 하고 삽입 하거나 삭제 작업 을 할 때 대량의 이동 이 필요 하 다.요소. 다음 절 에 서 는 이 문제 의 해결 방법 인 체인 저장 구 조 를 토론 할 것 이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
기초 정리 - 1문자 (String) 숫자 (Number) 불린 (Boolean) null undefined 심볼 (Symbol) 큰정수 (BigInt) 따옴표로 묶어 있어야 함 Not-A-Number - 숫자 데이터 / 숫자로 표...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
