数据结构 JS 版

2018-11-18 admin

内容:栈、队列、链表、集合、字典、散列表、树

  • 通过类封装实现栈结构,不直接继承数组的原生方法的原因是,数组具有某些其他数据结构的方法,为了只让栈暴露栈的方法,还得编写将非栈的方法封闭的代码,多了冗余代码,且不是面向对象编程的合理表现。
//栈,方法包括入栈操作、出栈操作、返回栈顶元素、判断栈是否为空、清空栈、栈的长度
//这里栈实例对象的方法都可看作闭包函数,items可看作类的私有变量,只有类实例的方法来访问,而items也是栈内容的存储实体。
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());

队列

//队列,方法包括入队操作、出队操作、返回队首元素、判断队列是否为空、清空队列、队列的长度
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;
    }
}

考虑到队列中每个元素具有优先级,所以队列中的元素采用对象来实现,具有两个属性:元素的值和元素的优先级。

//优先级队列
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<items.length;i++){
                if(items[i].priority > priority){
                    items.splice(i,0,queueElement);
                    break;
                }else if(i === (items.length-1)){
                    items.push(queueElement);
                    break;  // 这里一定要break,不然会循环插入,导致堆溢出
                }
            }
        }
    };
    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;
    }
}

可以换个角度想:一排凳子,所有人循环去坐,击鼓之后,坐在第一个凳子(队头)上的人淘汰,即下面代码参考的思路。

//循环队列
//击鼓传花游戏,以固定循环次数来模拟每轮击鼓的固定时长,该游戏会一轮一轮迭代,每轮淘汰一人,直到只剩最后一人即为胜者
function hotPotato(namelist,num){
    var queue = new Queue();
    for(var i=0;i<namelist.length;i++){
        queue.inqueue(namelist[i]);
    }
    while(queue.size() > 1){
        for(i=0;i<num;i++){
            var nowElement = queue.front();
            queue.outqueue();
            queue.inqueue(nowElement);
        }
        var deletElement = queue.front();
        queue.outqueue();
        console.log(deletElement+"在击鼓传花游戏中被淘汰");
    }
    return queue.front();
}
var list = ["hahah","askdjvzxv","uuuuu","aaaaa","bbbbbb","ccccc"];
var winner = hotPotato(list,5);
console.log("胜利者是:"+winner);

链表

  • 由于链表中每个元素都有指向下一个元素的指针,所以链表中每个元素利用对象来实现,对象具有两个属性:元素的值和指向下一个元素的指针;在指定位置插入或删除元素,都需要注意与前一个和后一个元素之间指针的关系;
//链表,元素在内存中非连续放置,方法包括链表尾部加入/删除元素,链表指定位置加入/删除元素,找出元素在链表中的索引,链表是否为空,链表的长度
function LinkedList(){
    var head = null;//链表第一个元素的引用
    var length = 0;//链表的长度,不然寻求size很麻烦
    var end = null;//链表最后一个元素的引用,方便插入/删除元素
    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){ //永远检测用户输入
            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<length;i++){
            iterNode = iterNode.next;
            outString.push(iterNode.element);
        }
        return outString;
    }
    //封装一个可共用的函数,找出指定位置的node元素
    this.findNodeAt = function(position){
        var iterNode = head;
        while(position > 1){
            iterNode = iterNode.next;
            position--;
        }
        return iterNode;
    }
}

集合

  • 采用对象来实现集合,对象的属性存放元素值,因为对象中的属性无序,可以很好地模拟集合的特性
//集合,集合类的方法包括添加/删除元素,是否有某值,清除集合,集合大小
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); //返回对象自身中可枚举属性
    }

    //集合的交集,并集,差集,子集方法
    //并集
    this.union = function(setB){
        var setAvalues = this.values();
        var setUnion = new Set();
        for(var i=0;i<setAvalues.length;i++){
            setUnion.add(setAvalues[i]);
        }
        var setBvalues = setB.values();
        for(var j=0;j<setBvalues.length;j++){
            setUnion.add(setBvalues[j]);
        }
        return setUnion;
    }
    //交集
    this.intersection = function(setB){
        var setAvalues = this.values();
        var intersectionSet = new Set();
        var setBvalues = setB.values();
        for(var i=0;i<setAvalues.length;i++){
            if(setB.has(setAvalues[i])){
                intersectionSet.add(setAvalues[i]);
            }
        }
        return intersectionSet;
    }
    //差集
    this.difference = function(setB){
        var setAvalues = this.values();
        var differenceSet = new Set();
        var setBvalues = setB.values();
        for(var i=0;i<setAvalues.length;i++){
            if(!setB.has(setAvalues[i])){
                differenceSet.add(setAvalues[i]);
            }
        }
        return differenceSet;
    }
    //子集
    this.isSubsetOf = function(setB){
        var setAvalues = this.values();
        var setBvalues = setB.values();
        for(var i=0;i<setAvalues.length;i++){
            if(!setB.has(setAvalues[i])){
                return false;
            }
        }
        return true;
    }
}

字典

//采用对象来实现字典,以key-value的形式存储,因为对象中的属性无序,字典的方法包括通过key来添加/删除元素,是否有某值,清除字典,字典大小
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); //返回对象自身中可枚举属性
    }
    this.values = function(){
        var res = [];
        for(key in items){
            if(items.hasOwnProperty(key)){
                res.push(items[key]);
            }
        }
        return res;
    }
    //获取整个字典对象
    this.getItems = function(){
        return items; 
    }

}

二叉搜索树

  • 二叉搜索树中每个节点都有三个属性。值,左引用,右引用。
  • 注意在实现时,拿到节点对象的引用,并不能对节点本身进行删除,最好删除节点的方法是将上一个节点的引用指向置为null,并将节点对象的引用置为null(释放内存,通知垃圾回收)
//二叉搜索树
function BinarySearchTree(){
    var rootNode = null;
    function TreeNode(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }
    //向树中插入新节点
    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("没有节点");
        }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("没有节点");
        }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("没有节点");
        }else{
            postraverse(rootNode);
        }
    }
    function postraverse(node){
        if(node !== null){
            postraverse(node.left);
            postraverse(node.right);
            console.log(node.key);
        }
    }
    //移除树中的节点
    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; //与下面三个return node的功能都是保证removeNode的返回值为删除节点后树的根节点
        }else if(key > node.key){
            node.right = removeNode(node.right,key);
            return node;
        }else{
            if(node !== null){ //考虑到被删除节点的三种情况
                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;
    }
    //查找某个节点
    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;
    }
    //获取树中最小值
    this.min = function(){
        var node = rootNode;
        while(node.left !== null){
            node = node.left;
        }
        return node.key;
    }
    //获取树中最大值
    this.max = function(){
        var node = rootNode;
        while(node.right !== null){
            node = node.right;
        }
        return node.key;
    }
    this.getRootNodeKey = function(){
        return rootNode.key;
    }
}

原文链接:https://segmentfault.com/a/1190000017053715

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-45810.html

文章标题:数据结构 JS 版

相关文章
Vue.js组件tab实现选项卡切换
本文实例为大家分享了vue插件tab选项卡的具体代码,供大家参考,具体内容如下 效果图: 代码如下: &lt;!DOCTYPE html&gt; &lt;html lang=&quot;en&quot;&gt; &lt;head&gt; ...
2017-03-13
JavaScript教程:JS中的原型
Keith Peters 几年前发表的一篇博文,关于学习没有“new”的世界,其中解释了使用原型继承代替构造函数。两者都是纯粹的原型编码。 标准方法(The Standard Way) 一直以来,我们学习的在 JavaScript 里创建对...
2015-11-12
three.js实现围绕某物体旋转
话不多说,请看代码: 可以拖动右上角观察变化 &lt;!DOCTYPE html&gt; &lt;html lang=&quot;en&quot; style=&quot;width: 100%; height:100%;&quot;&gt...
2017-02-17
NodeJS参考手册pdf版
下载地址:Nodejs参考手册PDF版下载 ...
2015-11-12
Node.js学习(1)----HTTP服务器与客户端
Node.js 标准库提供了 http 模块,其中封装了一个高效的 HTTP 服务器和一个简易的HTTP 客户端。http.Server 是一个基于事件的 HTTP 服务器,它的核心由 Node.js 下层 C++部分实现,而接口由 Jav...
2015-11-12
Riot.js:不足1KB的MVP客户端框架
Riot.js是一款MVP(模型-视图-呈现)开源客户端框架,其最大的特点就是体积非常小,不足1KB,虽然体积小,但它可以帮助用户构建大规模的Web应用程序。 Riot.js是由Moot公司开发,目前最新版本为v0.9.2,遵循MIT开源许...
2016-03-11
使用jspdf生成pdf报表
由于前台html已经动态生成报表,而且,前台有一个功能,一个date range组件,当你拖动的时候,报表会在不提交到后台的情况下动态变化。 因此需要用到js生成生报表: 用到的组件: jquery.js jspdf.js canvg.js...
2017-03-25
AngularJS vs. jQuery,看看谁更胜一筹
很多Web开发新手都会有这样的疑问“我应该使用什么开发框架呢,如何快速学会Web开发呢?”这个问题其实没有一个统一的正确答案,其中讨论最多的就是AngularJS和jQuery的差别。这两者的之间的比较很微妙,有时就像拿苹果和橘子在作比较,...
2015-11-12
如何为高负载网络优化Nginx 和 Node.js?
译者:AlfredCheung 在搭建高吞吐量web应用这个议题上,NginX和Node.js可谓是天生一对。他们都是基于事件驱动模型而设计,可以轻易突破Apache等传统web服务器的C10K瓶颈。预设的配置已经可以获得很高的并发,不过,...
2015-11-12
javaScript+turn.js实现图书翻页效果实例代码
为了实现图书翻页的效果我们在网上可以看到很多教程 在这里推荐turn.js 网上的turn.js 有api 不过是英文的  很多人看起来不方便 .关于代码也是奇形怪状在这里我将详细讲解如何使用turn.js实现翻页效果 ,本篇文章只是讲解 ...
2017-03-16
回到顶部