JavaScript数据结构

2019-02-27 本文已影响0人 zhoulh_cn

数组

数组实现

创建和初始化数组

var daysOfWeek=[];
daysOfWeek=['Sunday', 'Monday', 'Tuesday', 'Wednesday','Thursday', 'Friday', 'Saturday'];

访问和迭代数组

for (var i=0;i<daysOfWeek.length;i++){
    console.log(daysOfWeek[i]);
}

添加元素

//尾添加
numbers.push(12, 13);
//or
numbers[numbers.length]=10;
//首添加
numbers.unshift(-4, -3);
//or
for(var i=numbers.length;i>0;i--){
    numbers[i]=numbers[i-1];
}
numbers[0]=-1;

删除元素

//尾删除
numbers.pop();
//or
numbers.length=numbers.length-1;
//首删除
numbers.shift();
//or
for(var i=0;i<numbers.length;i++){
    numbers[i]=numbers[i+1];
}
numbers.length=numbers.length-1;

在任意位置添加和删除元素

//添加
numbers.splice(5,0,2,3,4);
//删除
numbers.splice(5,3);

JavaScript数组的其他方法

数组合并

var zero=0;
var positiveNumbers=[1,2,3];
var negativeNumbers=[-3,-2,-1];
var numbers=negativeNumbers.concat(zero, positiveNumbers);

迭代器函数

var isEven=function(item){
   return (x%2==0)?true:false;
}
//every，每一项返回true时，整体返回true
numbers.every(isEven);
//some，任意一项返回true，整体返回true
numbers.some(isEven);
//filter，整体返回由返回值为true的项组成的数组
var evenNumbers=numbers.filter(isEven);
//map，整体返回由返回值组成的数组
var myMap=numbers.map(isEven);
//reduce，整体返回叠加的值
numbers.reduce(function(previous, current, index){
   return previous + current;
});
//forEach，对数组每一项执行传入函数
numbers.forEach(function(x){
   console.log((x % 2 == 0));
});

栈（LIFO）

栈实现

function Stack(){
    let items=[];
    //向栈添加元素
    this.push=function(element){
        items.push(element);
    };
    //从栈移除元素
    this.pop=function(){
        return items.pop();
    };
    //查看栈顶元素
    this.peek=function(){
        return items[items.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());
    };
}
//使用Stack类
let stack=new Stack();

ECMAScript 6 实现Stack 类

ES6声明Stack类

class Stack{
    constructor(){
        this.items=[];
    }
    push(element){
        this.items.push(element);
    }
    //其他方法
}

队列（FIFO）

队列实现

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());
    };
}
//使用Queue类
let queue=new Queue();

链表

数组的缺点：

大小固定
移动数据成本高
数据存储需要连续的空间

链表的缺点：

获取数据成本高

实现单向链表

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);
        let current;
        //空链表
        if(head===null){
            head=node;
        }else{
            current=head;
            while(current.next){
                current=current.next;
            }
            current.next=node;
        }
        length++;
    };
    this.insert=function(position,element){
        //检查越界
        if(position>=0&&position<=length){
            let node=new Node(element);
            let current=head;
            let previous;
            let index=0;
            if(position===0){
                node.next=current;
                head=node;
            }else{
                while(index<position){
                    previous=current;
                    current=current.next;
                    index++;
                }
                node.next=current;
                previous.next=node;
            }
            length++;
            return true;
        }else{
            return false;
        }
    };
    this.removeAt=function(position){
        //检查越界
        if(position>=0&&position<length){
            let current=head;
            let previous;
            index=0;
            if(position===0){
                head=current.next;
            }else{
                while(index<position){
                    previous=current;
                    current=current.next;
                    index++;
                }
                previous.next=current.next;
            }
            length--;
            return current.element;
        }else{
            return null;
        }
    };
    this.indexOf=function(element){
        let current=head;
        let index=0;
        while(current){
            if(element===current.element){
                return index;
            }
            index++;
            current=current.next;
        }
        return -1;
    };
    this.remove=function(element){
        let index=this.indexOf(element);
        return this.removeAt(index);
    };
    this.toString=function(){
        let current=head;
        let string='';
        while(current){
            string+=current.element+(current.next?'n':'');
            current=current.next;
        }
        return string;
    };
    this.isEmpty=function(){
        return length===0;
    };  
    this.size=function(){
        return length;
    };
    this.getHead=function(){
        return head;
    };
}

实现双向链表

function DoublyLinkedList(){
    let Node=function(element){
        this.element=element;
        this.next=null;
        this.prev=null;
    };
    let length=0;
    let head=null;
    let tail=null;
    this.insert=function(position,element){
        //检查越界
        if(position>=0&&position<=length){
            let node=new Node(element);
            let current=head;
            let previous;
            let index=0;
            if(position===0){
                if(!head){
                    head=node;
                    tail=node;
                }else{
                    node.next=current;
                    current.prev=node;
                    head=node;
                }
            }else if(position===length){
                current=tail;
                current.next=node;
                node.prev=current;
                tail=node;
            }else{
                while(index<position){
                    previous=current;
                    current=current.next;
                    index++;
                }
                node.next=current;
                current.prev=node;
                previous.next=node;
                node.prev=previous;
            }
            length++;
            return true;
        }else{
            return false;
        }
    };
    this.removeAt=function(position){
        if(position>=0&&position<length){
            let current=head;
            let previous;
            let index=0;
            if(position===0){
                head=current.next;
                if(length===1){
                    tail=null;
                }else{
                    head.prev=null;
                }
            }else if(position===length-1){
                current=tail;
                tail=current.prev;
                tail.next=null;
            }else{
                while(index<position){
                    previous=current;
                    current=current.next;
                    index++;
                }
                previous.next=current.next;
                current.next.prev=previous;
            }
            length--;
            return current.element;
        }else{
            return null;
        }
    }
}

集合

集合是由一组无序且唯一（即不能重复）的项组成的，ECMAScript 6原生支持Set类

集合实现

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

实现集合操作

并集

function Set(){
    //其他实现代码

    //Set类的union方法
    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;
    }
}

交集

function Set(){
    //其他实现代码

    this.intersection=function(otherSet){
        let intersectionSet=new Set();
        let values=this.values();
        for(let i=0;i<values.length;i++){
            if(otherSet.has(values[i])){
                intersectionSet.add(values[i]);
            }
        }
        return intersectionSet;
    }
}

差集

function Set(){
    //其他实现代码

    this.difference=function(otherSet){
        let differenceSet=new Set();
        let values=this.values();
        for(i=0;i<values.length;i++){
            if(otherSet.has(values[i])){
                differenceSet.add(values[i]);
            }
        }
        return differenceSet;
    }
}

子集

function Set(){
    //其他实现代码

    this.subset=function(otherSet){
        if(this.size()>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(){
    let items={};
    this.has=function(key){
        return key in items;
    };
    this.set=function(key,value){
        items[key]=value;
    };
    this.delete=function(key){
        if(this.has(key)){
            delete items[key];
            return true;
        }
        return false;
    };
    this.get=function(key){
        return this.has(key)?items[key]:undefined;
    };
    this.values=function(){
        let values=[];
        for(let key in items){
            values.push(items[key]);
        }
        return values;
    };
    this.keys=function(){
        return Object.keys(items);
    };
    this.getItems=function(){
        return items;
    };
}
//使用Dictionary 类
let dictionary=new Dictionary();

散列映射和字典一样键是唯一的，散列映射的键对应的散列值代表实际值在散列表中的地址
散列函数：键值经过散列函数得到散列值

散列表实现

function HashTable(){
    let table=[];
    //散列函数
    let loseloseHashCode=function(key){
        let hash=0;
        for(let i=0;i<key.length;i++){
            hash+=key.charCodeAt(i);
        }
        return hash%37;
    };
    this.put=function(key,value){
        let 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;
    };
}
//使用 HashTable 类
let hash=new HashTable();

散列集合和集合一样值是唯一的，散列的值对应的散列值代表实际值在散列表中的地址
散列函数：实际值经过散列函数得到散列值

树

树和散列映射一样是非顺序数据结构，对于存储需要快速查找的数据非常有用

tree.jpg

位于树顶部的节点叫作根节点（11）。它没有父节点。树中的每个元素都叫作节点，节点分
为内部节点和外部节点。至少有一个子节点的节点称为内部节点（7、5、9、15、13和20是内部
节点）。没有子元素的节点称为外部节点或叶节点（3、6、8、10、12、14、18和25是叶节点）
一个节点可以有祖先和后代。一个节点（除了根节点）的祖先包括父节点、祖父节点、曾祖
父节点等。一个节点的后代包括子节点、孙子节点、曾孙节点等。例如，节点5的祖先有节点7
和节点11，后代有节点3和节点6
有关树的另一个术语是子树。子树由节点和它的后代构成。例如，节点13、12和14构成了上
图中树的一棵子树
节点的一个属性是深度，节点的深度取决于它的祖先节点的数量。比如，节点3有3个祖先节
点（5、7和11），它的深度为3
树的高度取决于所有节点深度的最大值。一棵树也可以被分解成层级。根节点在第0层，它
的子节点在第1层，以此类推。上图中的树的高度为3（最大高度已在图中表示——第3层）

二叉树和二叉搜索树
二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。
二叉搜索树（BST）是二叉树的一种，但是它只允许你在左侧节点存储（比父节点）小的值，
在右侧节点存储（比父节点）大（或者等于）的值

实现二叉搜索树

function BinarySearchTree(){
    let Node=function(key){
        this.key=key;
        this.left=null;
        this.right=null;
    };
    let root=null;
    //插入节点方法
    this.insert=function(key){
        let newNode=new Node(key);
        if(root===null){
            root=newNode;
        }else{
            insertNode(root.newNode);
        }
    };
    //插入节点辅助函数
    let 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.inOrderTraverse=function(callback){
        inOrderTraverseNode(root,callback);
    };
    let inOrderTraverseNode=function(node,callback){
        if(node!==null){
            inOrderTraverseNode(node.left,callback);
            callback(node.key);
            inOrderTraverseNode(node.right,callback);
        }
    };
    //树的遍历-先序遍历
    this.preOrderTraverse=function(callback){
        preOrderTraverseNode(root,callback);
    };
    let preOrderTraverseNode=function(node,callback){
        if(node!==null){
            callback(node.key);
            preOrderTraverseNode(node.left,callback);
            preOrderTraverseNode(node.right,callback);
        }
    };
    //树的遍历-后序遍历
    this.postOrderTraverse=function(callback){
        postOrderTraverseNode(root,callback);
    };
    let postOrderTraverseNode=function(node,callback){
        if(node!==null){
            postOrderTraverseNode(node.left,callback);
            postOrderTraverseNode(node.right,callback);
            callback(node.key);
        }
    };
    //搜索树中的值
    //搜索最小值
    this.min=function(){
        return minNode(root);
    };
    let minNode=function(node){
        if(node){
            while(node&&node.left!==null){
                node=node.left;
            }
            return node.key;
        }
        return null;
    };
    //搜索最大值
    this.max=function(){
        return maxNode(root);
    };
    let 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);
    };
    let 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);
    };
    let 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{
            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.right;
                return node;
            }
            let aux=findMinNode(node.right);
            node.key=aux.key;
            node.right=removeNode(node.right,aux.key);
            return node;
        }
    };
    let findMinNode=function(node){
        while(node&&node.left!==null){
            node=node.left;
        }
        return node;
    };
    
}
let tree=new BinarySearchTree();
function printNode(value){
    console.log(value);
}
//调用中序遍历
tree.inOrderTraverse(printNode);
//调用先序遍历
tree.preOrderTraverse(printNode);
//调用后序遍历
tree.postOrderTraverse(printNode);