數(shù)據(jù)結(jié)構(gòu) JS 版

sarva 發(fā)布于2019-08-26 12:25 / 1183人閱讀

摘要：內(nèi)容棧隊(duì)列鏈表集合字典散列表樹(shù)棧通過(guò)類封裝實(shí)現(xiàn)棧結(jié)構(gòu)，不直接繼承數(shù)組的原生方法的原因是，數(shù)組具有某些其他數(shù)據(jù)結(jié)構(gòu)的方法，為了只讓棧暴露棧的方法，還得編寫(xiě)將非棧的方法封閉的代碼，多了冗余代碼，且不是面向?qū)ο缶幊痰暮侠肀憩F(xiàn)。

內(nèi)容：棧、隊(duì)列、鏈表、集合、字典、散列表、樹(shù)

棧

通過(guò)類封裝實(shí)現(xiàn)棧結(jié)構(gòu)，不直接繼承數(shù)組的原生方法的原因是，數(shù)組具有某些其他數(shù)據(jù)結(jié)構(gòu)的方法，為了只讓棧暴露棧的方法，還得編寫(xiě)將非棧的方法封閉的代碼，多了冗余代碼，且不是面向?qū)ο缶幊痰暮侠肀憩F(xiàn)。

//棧，方法包括入棧操作、出棧操作、返回棧頂元素、判斷棧是否為空、清空棧、棧的長(zhǎng)度
//這里棧實(shí)例對(duì)象的方法都可看作閉包函數(shù)，items可看作類的私有變量，只有類實(shí)例的方法來(lái)訪問(wèn)，而items也是棧內(nèi)容的存儲(chǔ)實(shí)體。
function Stack(){
    var items = [];
    this.push = function(ele){
        items.push(ele);
    };
    this.pop = function(){
        items.pop();
    };
    this.size = function(){
        return items.length;
    };
    this.clear = function(){
        items = [];
    };
    this.peek = function(){
        return items[items.length-1];
    }
    this.isEmpty = function(){
        return items.length > 0 ? false : true;
    }
}
var stack = new Stack();
console.log(stack);
stack.push(2);
console.log(stack.size());
console.log(stack.isEmpty());

隊(duì)列

基礎(chǔ)實(shí)現(xiàn)

//隊(duì)列，方法包括入隊(duì)操作、出隊(duì)操作、返回隊(duì)首元素、判斷隊(duì)列是否為空、清空隊(duì)列、隊(duì)列的長(zhǎng)度
function Queue(){
    var items = [];
    this.inqueue = function(ele){
        items.push(ele);
    };
    this.outqueue = function(){
        items.shift();
    };
    this.size = function(){
        return items.length;
    };
    this.clear = function(){
        items = [];
    };
    this.front = function(){
        return items[0];
    }
    this.isEmpty = function(){
        return items.length > 0 ? false : true;
    }
}

優(yōu)先級(jí)隊(duì)列

考慮到隊(duì)列中每個(gè)元素具有優(yōu)先級(jí)，所以隊(duì)列中的元素采用對(duì)象來(lái)實(shí)現(xiàn)，具有兩個(gè)屬性：元素的值和元素的優(yōu)先級(jí)。

//優(yōu)先級(jí)隊(duì)列
function PriorityQueue(){
    var items = [];
    function QueueElement(element,priority){
        this.element = element;
        this.priority = priority;
    }
    this.inqueue = function(element,priority){
        var queueElement = new QueueElement(element,priority);
        if(this.isEmpty()){
            items.push(queueElement);
        }else{
            for(var i=0;i priority){
                    items.splice(i,0,queueElement);
                    break;
                }else if(i === (items.length-1)){
                    items.push(queueElement);
                    break;  // 這里一定要break，不然會(huì)循環(huán)插入，導(dǎo)致堆溢出
                }
            }
        }
    };
    this.outqueue = function(){
        items.shift();
    };
    this.size = function(){
        return items.length;
    };
    this.clear = function(){
        items = [];
    };
    this.front = function(){
        return items[0].element;
    }
    this.isEmpty = function(){
        return items.length > 0 ? false : true;
    }
    this.get = function(){
        return items;
    }
}

循環(huán)隊(duì)列/擊鼓傳花游戲

可以換個(gè)角度想：一排凳子，所有人循環(huán)去坐，擊鼓之后，坐在第一個(gè)凳子（隊(duì)頭）上的人淘汰，即下面代碼參考的思路。

//循環(huán)隊(duì)列
//擊鼓傳花游戲，以固定循環(huán)次數(shù)來(lái)模擬每輪擊鼓的固定時(shí)長(zhǎng)，該游戲會(huì)一輪一輪迭代，每輪淘汰一人，直到只剩最后一人即為勝者
function hotPotato(namelist,num){
    var queue = new Queue();
    for(var i=0;i 1){
        for(i=0;i
鏈表
由于鏈表中每個(gè)元素都有指向下一個(gè)元素的指針，所以鏈表中每個(gè)元素利用對(duì)象來(lái)實(shí)現(xiàn)，對(duì)象具有兩個(gè)屬性：元素的值和指向下一個(gè)元素的指針；在指定位置插入或刪除元素，都需要注意與前一個(gè)和后一個(gè)元素之間指針的關(guān)系；
//鏈表，元素在內(nèi)存中非連續(xù)放置，方法包括鏈表尾部加入/刪除元素，鏈表指定位置加入/刪除元素，找出元素在鏈表中的索引，鏈表是否為空，鏈表的長(zhǎng)度
function LinkedList(){
    var head = null;//鏈表第一個(gè)元素的引用
    var length = 0;//鏈表的長(zhǎng)度，不然尋求size很麻煩
    var end = null;//鏈表最后一個(gè)元素的引用，方便插入/刪除元素
    function Node(element){
        this.element = element;
        this.next = null;
    }
    //從鏈表尾部加入node元素
    this.appendList = function(element){
        var node = new Node(element);
        if(head === null){
            head = node;
        }else{
            end.next = node;
        }
        end = node;
        length++;
    };
    //從鏈表指定位置加入node元素,0表示在鏈表頭插入該元素
    this.appendListAt = function(position,element){
        var node = new Node(element);
        if(position > 0){
            var frontNode = this.findNodeAt(position);
            var afterNode = frontNode.next;
            frontNode.next = node;
            node.next = afterNode;
            length++;
        }else if(position === 0){
            node.next = head;
            head = node;
            length++;
        }
    };
    //從鏈表尾部刪除node元素
    this.removeList = function(){
        if(head !== null){
            var findNode = this.findNodeAt(length-1);
            end = findNode;
            findNode.next = null;
            length--;
        }
    };
    //從鏈表指定位置刪除node元素
    this.removeListAt = function(position){
        if(position > 1){ //永遠(yuǎn)檢測(cè)用戶輸入
            var frontNode = this.findNodeAt(position-1);
            var afterNode = frontNode.next.next;
            frontNode.next = afterNode;
            length--;
        }else if(position = 1){
            head = head.next;
            length--;
        }
    };
    //鏈表的大小
    this.size = function(){
        return length;
    };
    this.isEmpty = function(){
        return head === null ? true : false;
    }
    this.toString = function(){
        var iterNode = head;
        var outString = [];
        outString.push(head.element);
        for(var i=1;i 1){
            iterNode = iterNode.next;
            position--;
        }
        return iterNode;
    }
}
集合
采用對(duì)象來(lái)實(shí)現(xiàn)集合，對(duì)象的屬性存放元素值，因?yàn)閷?duì)象中的屬性無(wú)序，可以很好地模擬集合的特性
//集合，集合類的方法包括添加/刪除元素，是否有某值，清除集合，集合大小
function Set(){
    var items = {};
    this.has = function(value){
        return items.hasOwnProperty(value);
    }
    //向集合中添加元素
    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 false;
    }
    this.size = function(){
        return Object.keys(items).length;
    }
    this.clear = function(){
        items = {};
    }
    this.values = function(){
        return Object.keys(items); //返回對(duì)象自身中可枚舉屬性
    }

    //集合的交集，并集，差集，子集方法
    //并集
    this.union = function(setB){
        var setAvalues = this.values();
        var setUnion = new Set();
        for(var i=0;i
字典
有集合的實(shí)現(xiàn)類似
//采用對(duì)象來(lái)實(shí)現(xiàn)字典，以key-value的形式存儲(chǔ)，因?yàn)閷?duì)象中的屬性無(wú)序，字典的方法包括通過(guò)key來(lái)添加/刪除元素，是否有某值，清除字典，字典大小
function Dictionary(){
    var items = {};
    this.has = function(key){
        return items.hasOwnProperty(key);
    }
    //向字典中添加元素
    this.set = function(key,value){
        if(!this.has(key)){
            items[key] = value;
            return true;
        }
        return false;
    }
    //刪除字典中的元素
    this.remove = 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.size = function(){
        return Object.keys(items).length;
    }
    this.clear = function(){
        items = {};
    }
    this.keys = function(){
        return Object.keys(items); //返回對(duì)象自身中可枚舉屬性
    }
    this.values = function(){
        var res = [];
        for(key in items){
            if(items.hasOwnProperty(key)){
                res.push(items[key]);
            }
        }
        return res;
    }
    //獲取整個(gè)字典對(duì)象
    this.getItems = function(){
        return items; 
    }

}
二叉搜索樹(shù)

二叉搜索樹(shù)中每個(gè)節(jié)點(diǎn)都有三個(gè)屬性。值，左引用，右引用。
注意在實(shí)現(xiàn)時(shí)，拿到節(jié)點(diǎn)對(duì)象的引用，并不能對(duì)節(jié)點(diǎn)本身進(jìn)行刪除，最好刪除節(jié)點(diǎn)的方法是將上一個(gè)節(jié)點(diǎn)的引用指向置為null，并將節(jié)點(diǎn)對(duì)象的引用置為null（釋放內(nèi)存，通知垃圾回收）

//二叉搜索樹(shù)
function BinarySearchTree(){
    var rootNode = null;
    function TreeNode(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }
    //向樹(shù)中插入新節(jié)點(diǎn)
    this.insert = function(key){
        var treeNode = new TreeNode(key);
        if(rootNode === null){
            rootNode = treeNode;
        }else{
            insertNode(rootNode,treeNode);
        }
    }
    function insertNode(node,treeNode){
        if(treeNode.key < node.key){
            if(node.left === null){
                node.left = treeNode;
            }else{
                insertNode(node.left,treeNode);
            }
        }else if(treeNode.key > node.key){
            if(node.right === null){
                node.right = treeNode;
            }else{
                insertNode(node.right,treeNode);
            }
        }
    }
    //先序遍歷
    this.preOrderTraverse = function(){
        if(rootNode === null){
            console.log("沒(méi)有節(jié)點(diǎn)");
        }else{
            pretraverse(rootNode);
        }
    }
    function pretraverse(node){
        if(node !== null){
            pretraverse(node.left);
            console.log(node.key);
            pretraverse(node.right);
        }
    }
    //中序遍歷
    this.inOrderTraverse = function(){
        if(rootNode === null){
            console.log("沒(méi)有節(jié)點(diǎn)");
        }else{
            intraverse(rootNode);
        }
    }
    function intraverse(node){
        if(node !== null){
            console.log(node.key);
            intraverse(node.left);
            intraverse(node.right);
        }
    }
    //后序遍歷
    this.posOrderTraverse = function(){
        if(rootNode === null){
            console.log("沒(méi)有節(jié)點(diǎn)");
        }else{
            postraverse(rootNode);
        }
    }
    function postraverse(node){
        if(node !== null){
            postraverse(node.left);
            postraverse(node.right);
            console.log(node.key);
        }
    }
    //移除樹(shù)中的節(jié)點(diǎn)
    this.remove = function(key){
        rootNode = removeNode(rootNode,key);
    }
    function removeNode(node,key){
        if(node === null){
            return null;
        }
        if(key < node.key){
            node.left = removeNode(node.left,key);
            return node; //與下面三個(gè)return node的功能都是保證removeNode的返回值為刪除節(jié)點(diǎn)后樹(shù)的根節(jié)點(diǎn)
        }else if(key > node.key){
            node.right = removeNode(node.right,key);
            return node;
        }else{
            if(node !== null){ //考慮到被刪除節(jié)點(diǎn)的三種情況
                if((node.left === null) && (node.right === null)){
                    node = null;//這里只是為了垃圾回收node，下面作用都類似
                    return node;//這里才是刪除的功能，這里的返回是為了讓node.left = removeNode(node.left,key);中node.left=null;
                }else if((node.left === null) && (node.right !== null)){
                    var temp = node.right;
                    node = null;
                    return temp;
                }else if((node.left !== null) && (node.right === null)){
                    var temp = node.left;
                    node = null;
                    return temp;
                }else if((node.left !== null) && (node.right !== null)){
                    var findNode = findMin(node.right);
                    node.key = findNode.key;
                    node.right = removeNode(node.right,findNode.key);
                    return node;
                }
            }
        }
    }
    function findMin(node){
        while(node.left !== null){
            node = node.left;
        }
        return node;
    }
    //查找某個(gè)節(jié)點(diǎn)
    this.search = function(key){
        var node = rootNode;
        while((node !== null) && (node.key !== key)){
            if(key < node.key){
                node = node.left;
            }else if(key > node.key){
                node = node.right;
            }
        }
        return (node !== null) ? true : false;
    }
    //獲取樹(shù)中最小值
    this.min = function(){
        var node = rootNode;
        while(node.left !== null){
            node = node.left;
        }
        return node.key;
    }
    //獲取樹(shù)中最大值
    this.max = function(){
        var node = rootNode;
        while(node.right !== null){
            node = node.right;
        }
        return node.key;
    }
    this.getRootNodeKey = function(){
        return rootNode.key;
    }
}