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;
    }
}

es6 新增了Map类

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，而不是值或键构成的数组。

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);

一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点（除了顶部的第一个节点）以及零个或多个子节点；

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;
        }
    }
}

当树很深的时候，添加移除和搜索某个节点时引起一些性能问题。

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