javascript 데이터 구조 학습 노트

데이터 구조
배열
방법.

// 、  
var arr = [];
//     
arr.push(1, 2); // [1,2]
//     
arr.unshift(0); // [0, 1, 3]
//     
arr.pop(); // [0, 1] 
//     
arr.shift(); // [1]
//     
[1].concat([2]) // [1,2]

교체 기

every every 방법 은 false 로 돌아 갈 때 까지 배열 의 모든 요 소 를 교체 합 니 다.

some some 는 every 와 유사 하지만, some 방법 은 함수 가 true

로 돌아 갈 때 까지 배열 의 모든 요 소 를 교체 합 니 다.

forEach 와 for 순환 의 결과 가 같다

map 새로운 배열 [1,2].map(o => o * 2) // [2,4]

로 돌아 가기

filter 새로운 배열 [1,2].filter(o => o > 1) // [2]

로 돌아 가기

reduce [1,2].reduce((result, current) => result + current) // 3

for of for (let n of numbers) { console.log((n % 2 === 0) ? 'even' : 'odd')};

entries

const numbers = [1,2,3];
let aEntries = numbers.entries(); //          
console.log(aEntries.next().value); // [0, 1]   0   1
console.log(aEntries.next().value); // [1, 2]   1   2
console.log(aEntries.next().value); // [2, 3]   2   3

keys

const numbers = [1,2,3];
console.log(Object.keys(numbers)); // ['0','1','2'];

values

const numbers = [1,2,3];
console.log(Object.values(numbers)); // [1,2,3]

Array.from

Array.of

fill

copyWithin

sort

find

findIndex

includes

창고.
창고 는 일종 의 복종 이다
후진 선 출 원칙 의 질서 있 는 집합
이루어지다

function Stack() {
    let items = [];
    //       
    this.push = function(element) {
        items.push(element);
    }
    //       
    this.pop = function() {
        return items.pop();
    };
    //       
    this.peek = function() {
        return items[item.length - 1];
    }
    //        
    this.isEmpty = function() {
        return items.length == 0;
    }
    this.size = function() {
        return items.length;
    };
    //         
    this.clear = function() {
        items = [];
    };
    this.print = function() {
        console.log(items.toString());
    };
}

창고 로 문 제 를 해결 하 다.
접근 한 작업 이나 경로, 취 소 된 작업 등 을 저장 합 니 다.
대열
대기 열 은 FIFO (First In First Out, 먼저 나 가 는 것 을 먼저 하 는 서비스 라 고도 합 니 다) 를 따 릅 니 다.
이루어지다

function Queue() {
    let items = [];
    //        
    this.enqueue = function(element) {
        items.push(element);
    };
    //        
    this.dequeue = function() {
        return items.shift();
    };
    //        
    this.front = function() {
        return items[0];
    };
    //         
    this.isEmpty = function() {
        return items.length == 0;
    };
    this.size = function() {
        return items.length;
    };
    //       
    this.print = function() {
        console.log(items.toString());
    };
}

체인 테이블
링크 마을 의 굵 고 질서 있 는 요소 집합 이지 만 배열 과 달리 링크 의 요 소 는 메모리 에 연속 적 으로 배치 되 지 않 습 니 다.모든 요 소 는 하나의 저장 요소 자체 의 노드 와 다음 요 소 를 가리 키 는 참조 (포인터 나 링크 라 고도 함) 로 구성 된다.
전통 적 인 배열 에 비해 링크 의 장점 중 하 나 는 요 소 를 추가 하거나 제거 할 때 다른 요 소 를 이동 하지 않 아 도 된다 는 것 이다.그러나 체인 시 계 는 지침 을 사용 해 야 하기 때문에 체인 시 계 를 실현 할 때 추가 적 인 주의 가 필요 하 다.배열 의 또 다른 디 테 일 은 모든 위치 에 있 는 모든 요 소 를 직접 방문 할 수 있 는 것 입 니 다. 링크 중간 에 있 는 요 소 를 방문 하려 면 시작 점 (표 머리) 부터 필요 한 요 소 를 찾 을 때 까지 목록 을 교체 해 야 합 니 다.
이루어지다

function LinkedList() {
    let Node = function(element) {
        this.element = element;
        this.next = null;
    };

    let length = 0;
    let head = null;
    //          
    this.append = function(element) {
        let node = new Node(element),
        current;

        if (head === null) {
            head = node;
        } else {
            current = head;
            //     ，        
            while (current.next) {
                current = current.next;
            }
            //       ，  next  node，    
            current.next = node;
        }
        length++； //        
    }
    //         
    this.removeAt = function() {
        //      
        if (position > -1 && position < length) {
            let current = head,
            previous,
            index = 0;

            //      
            if (position === 0) {
                head = current.next;
            } else {
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                //  previous   current        ：   current，     
                previous.next = current.next;
            }
            length--;
            return current.element;
        } else {
            return null;
        }
    }
    //          
    this.insert = function(position, element) {
        //      
        if (position >= 0 && position <= length) {
            let node = new Node(element),
            current = head,
            previous,
            index = 0;

            if (position === 0) { //         
                node.next = current;
                head = node;
            } else {
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
            }
            length++; //        
            return true;
        } else {
            return false;
        }
    }
    // toString  
    this.toString = function() {
        let current = head,
        string = '';

        while (current) {
            string += current.element + (current.next ? 'n' : '');
            current = current.next;
        }
        
        return string;
    }
    // indexOf   
    this.indexOf = function(elment) {
        let current = head,
        index = 0;
        
        while(current) {
            if (element === current.element) {
                return index;
            }
            index++;
            current = current.next;
        }

        return -1;
    }
    // remove   
    this.remove = function(elment) {
        let index = this.indexOf(element);
        return this.removeAt(index);
    }
    // isEmpty   
    this.isEmpty = function() {
        return length == 0;
    }
    // size   
    this.size = function() {
        return length;
    }
    // getHead   
    this.getHead = function() {
        return head;
    }
}

쌍방 향 체인 시계.
집합 하 다.
집합 은 무질서 하고 유일 하 게 (즉 중복 할 수 없 음) 항목 으로 구 성 된 것 이다.이 데이터 구 조 는 유한 집합 과 같은 수학 개념 을 사 용 했 으 나 컴퓨터 과학 의 데이터 구조 에 응용 되 었 다.

function Set() {
    let items = {};
    // has   
    this.has = function(value) {
        return items.hasOwnProperty(value);
    };
    // add   
    this.add = function(value) {
        if (!this.has(value)) {
            items[value] = value;
            return true;
        }
        return false;
    }
    // remove   
    this.remove = function(value) {
        if (this.has(value)) {
            delete items[value];
            return true;
        }
        return false;
    }
    // clear   
    this.clear = function() {
        items = {};
    }
    // size   
    this.size = function() {
        return Object.keys(items).length;
    }
    // values   
    this.values = function() {
        let values = [];
        for (let i = 0, keys = Object.keys(items); i< keys.length; i++) {
            values.push(items[keys[i]]);
        }
        return values;
    }
    //   
    this.union = function(otherSet) {
        let unionSet = new Set();

        let values = this.values();
        for (let i = 0; i < values.length; i++) {
            unionSet.add(values[i]);
        }

        values = otherSet.values();
        for (let i = 0; i < values.length; i++) {
            unionSet.add(values[i]);
        }

        return unionSet;
    }
    //   
    this.intersection = function(otherSet) {
        let intersectionSet = new Set();

        let values = this.values();
        for (let i = 0;i otherSet.size()) {
            return false;
        } else {
            let values = this.values();
            for (let i = 0;i< values.length;i++) {
                if (!otherSet.has(values[i])) {
                    return false;
                }
            }
            return true;
        }
    }
}

사전 과 산 목록
이루어지다

function Dictionary() {
    var items = {};
    // has   set   
    this.has = function(key) {
        return items.hasOwnProperty(key);
    }
    this.set = function(key, value) {
        item[key] = value;
    }
    // delete   
    this.delete = function(key) {
        if (this.has(key)) {
            delete items[key];
            return true;
        }
        return false;
    }
    // get   values   
    this.get = function(key) {
        return this.has(key) ? items[key] : undefined;
    }
    this.values = function() {
        var values = [];
        for(var k in items) {
            if (this.has(k)) {
                values.push(items[k]);
            }
        }

        return values;
    }
    // clear   
    this.clear = function() {
        items = {};
    }
    // size   
    this.size = function() {
        return Object.keys(items).length;
    }
    // keys   
    this.keys = function() {
        return Object.keys(items);
    }
    // getItems   
    this.getItems = function() {
        return items;
    }

}

산 목록
HashTable 류 는 HashMap 류 라 고도 하 는데 Dictionary 류 의 산 목록 이 실현 방식 입 니 다.
해시 알고리즘 의 역할 은 가능 한 한 빨리 데이터 구조 에서 값 을 찾 는 것 이다.

function HashTable() {
    var table = [];
    var loseloseHashCode = function(key) {
        var hash = 0;
        for (var i = 0; i< key.length; i++) {
            hash += key.charCodeAt(i);
        }
        return hash % 37;
    }
    this.put = function(key, value) {
        var position = loseloseHashCode(key);
        console.log(position + ' - ' + key);
        table[position] = value;
    }
    this.get = function(key) {
        return table[loseloseHashCode(key)];
    }
    this.remove = function(key) {
        table[loseloseHashCode(key)] = undefined;
    }
}

지도 류
맵 클래스 추가

var map = new Map();

map.set('a', 'b');

console.log(map.has('a')); // true
console.log(map.size()); //   1
console.log(map.keys()); // ['a']
console.log(map.values()); // ['b'];

//  Dictionary   ，es6 Map  values   keys     Iterator，           。

es6 --- WeakMap 류 와 WeakSet 류

WeakMap 과 WeakSet 류 에는 entries keys values 등 방법 이 없습니다

대상 만 키

var map = new WeakMap();
var obj = {name: 'a'};
map.set(obj, 'b');

console.log(map.has(obj)); //   true
console.log(map.get(obj)); //   'b'
map.delete(obj);

나무.
하나의 나무 구 조 는 부자 관계 가 존재 하 는 일련의 노드 를 포함한다.모든 노드 에는 부모 노드 (상단 의 첫 번 째 노드 제외) 와 0 개 또는 여러 개의 키 노드 가 있다.
이 진 트 리 와 이 진 트 리 검색

function BinarySearchTree() {
    var Node = function(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }

    var root = null;

    var insertNode = function(node, newNode) {
        if (newNode.key < node.key) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                insertNode(node.right, newNode);
            }
        }
    }
    //         
    this.insert = function(key) {
        var newNode = new Node(key);

        if (root = null) {
            root = newNode;
        } else {
            insertNode(root, newNode);
        }
    }

    var inOrderTraverseNode = function(node, callback) {
        if (node !== null) {
            inOrderTraverseNode(node.left, callback);
            callback(node.key);
            inOrderTraverseNode(node.right, callback);
        }
    }

    //     
    this.inOrderTraverse = function(callback) {
        inOrderTraverseNode(root, callback);
    }

    var preOrderTraverseNode = function(node, callback) {
        if (node !== null) {
            callback(node.key);
            preOrderTraverseNode(node.left, callback);
            preOrderTraverseNode(node.right, callback);
        }
    }

    //     
    this.preOrderTraverse = function(callback) {
        preOrderTraverseNode(root, callback);
    }

    var postOrderTraverseNode = function(node, callback) {
        if (node !== null) {
            postOrderTraverseNode(node.left, callback);
            postOrderTraverseNode(node.right, callback);
            callback(node.key);
        }
    }

    //     
    this.postOrderTraverse = function(callback) {
        postOrderTraverseNode(root, callback);
    }

    //      
    this.min = function() {
        return minNode(root);
    }

    var minNode = function(node) {
        if (node) {
            while( node && node.left !== null) {
                node = node.left;
            }
            return node.key;
        }
        return null;
    }

    //      
    this.max = function() {
        return maxNode(root);
    }

    var maxNode = function(node) {
        if (node) {
            while(node && node.right !== null) {
                node = node.right;
            }
            return node.key;
        }
        return null;
    }

    //         
    this.search = function(key) {
        return searchNode(root, key);
    }

    var searchNode = function(node, key) {
        if (node === null) {
            return false;
        }
        if (key < node.key) {
            return searchNode(node.left, key);
        } else if (key > node.key) {
            return searchNode(node.right, key);
        } else {
            return true;
        }
    }

    //       
    this.remove = function(key) {
        root = removeNode(root, key);
    }

    var removeNode = function(node, key) {
        if (node === null) {
            return null;
        }
        if (key < node.key) {
            node.left = removeNode(node.left,key);
            return node;
        } else if (key > node.key) {
            node.right = removeNode(node.right,key);
            return node;
        } else { //    node.key
            //      --     
            if (node.left === null && node.right === null) {
                node = null;
                return node;
            }

            //      --            
            if (node.left === null) {
                node = node.right;
                return node;
            } else if (node.right === null) {
                node = node.left;
                return node;
            }

            //      ----            
            var aux = findMinNode(node.right);
            node.key = aux.key;
            node.right = removeNode(node.rihgt, aux.key);
            return node;
        }

        var findMinNode = function(node) {
            while (node && node.left !== null) {
                node = node.left;
            }
            return node;
        }
    }
}

셀 프 밸 런 스 트 리 (AVL)
나무 가 깊 을 때 노드 를 제거 하고 검색 할 때 성능 문제 가 발생 합 니 다.

var heightNode = function(node) {
    if (node === null) {
        return -1;
    } else {
        return Math.max(heightNode(node.left), heightNode(node.right)) + 1;
    }
}

var rotationRR = function(node) {
    var tmp = node.right;
    node.right = tmp.left;
    tmp.left = node;
    return tmp;
}
var rotationLL = function(node) {
    var tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    return tmp;
}

var rotationLR = function(node) {
    node.left = rotationRR(node.left);
    return rotationLL(node);
}

var rotationRL = function(node) {
    node.right = rotationLL(node.right);
    return rotationRR(node);
}

var insertNode = function(node, element) {
    if (node === null) {
        node = new Node(element);
    } else if (element < node.key) {
        node.left = insertNode(node.left, element);

        if (node.left !== null) {
            //         
            if ((heightNode(node.left) - heightNode(node.right) > 1)) {
                if (element < node.left.key) {
                    node = rotationLL(node);
                } else {
                    node = rotationLR(node);
                }
            }
        }
    } else if (element > node.key) {
        node.right = insertNode(node.right, element);

        if (node.right !== null) {
            //         
            if ((heightNode(node.right) - heightNode(node.left) > 1)) {
                if (element > node.right.key) {
                    node = rotationRR(node);
                } else {
                    node = rotationRL(node);
                }
            }
        }
    }
    return node;
}

그림.
그림 은 네트워크 구조의 추상 적 인 모델 로 그림 은 가장자리 로 연 결 된 노드 (또는 정점) 이다. 학습 그림 은 중요 하 다. 모든 관 계 를 그림 으로 표시 할 수 있 기 때문이다.

function Graph() {
    var vertices = [];
    var adjList = new Dictionary();

    this.addVertex = function(v) {
        vartices.push(v);
        adjList.set(v, []);
    }

    this.addEdge = function(v, w) {
        addList.get(v).push(w);
        addList.get(w).push(v);
    }

    this.toString = function() {
        var s = '';
        for (var i = 0; i< vertices.length;i++) {
            s += vertices[i] + ' -> ';
            var neighbors = adjList.get(vertices[i]);
            for (var j = 0;j

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Thymeleaf 의 일반 양식 제출 과 AJAX 제출

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

javascript 데이터 구조 학습 노트

좋은 웹페이지 즐겨찾기