美文网首页
js数据结构和算法

js数据结构和算法

作者: 易路先登 | 来源:发表于2021-08-17 06:56 被阅读0次

队列

FIFO(first in first out): 先入后厨
队列的实现

class Queue{
            constructor(){
                this.container = []
            }
            enQueue(value){
                this.container.push(value)
            }
            deQueue(){
                return this.container.shift()
            }
            size(){
                return this.container.length
            }
        }

案例问题

1.首先，我们先来了解一下什么是约瑟夫环问题：

讲一个比较有意思的故事：约瑟夫是犹太军队的一个将军，在反抗罗马的起义中，他所率领的军队被击溃，只剩下残余的部队40余人，他们都是宁死不屈的人，所以不愿投降做叛徒。一群人表决说要死，所以用一种策略来先后kill所有人。
于是约瑟夫建议：每次由其他两人一起kill一个人，而被kill的人的先后顺序是由抽签决定的，约瑟夫有预谋地抽到了最后一签，在kill了除了他和剩余那个人之外的最后一人，他劝服了另外一个没死的人投降了罗马。

我们这个规则是这么定的：
在一间房间总共有n个人（下标0～n-1），只能有最后一个人活命。

按照如下规则去排除人：

所有人围成一圈
顺时针报数，每次报到q的人将被排除掉
被排除掉的人将从房间内被移走
然后从被kill掉的下一个人重新报数，继续报q，再清除，直到剩余一人
你要做的是：当你在这一群人之间时，你必须选择一个位置以使得你变成那剩余的最后一人，也就是活下来。

 let first = new Queue()
        //入队40人
        for(let i = 0;i < 40;i++){
            first.enQueue(i+1)
        }
        let number=0;
        let result = []
        while(first.size()>3){
            let outPerson = first.deQueue()
            number++
            if(number===9){
                number=0
                result.push(outPerson)
            }else{
                first.enQueue(outPerson)
            }
}
console.log(first,result)

链表

单向链表

 //[1,'2',3,8,4,5]
        //数组的变量名其实是一个地址值，指向内存中该数组的第一个元素 
        //&    具体取值时是怎么计算的呢  首地址+宽度*索引
        //链表
        //{{value:1,next:obj1}}  var obj1 = {value:3,next:obj2}
        class LinkNode{
            constructor(value,next){
                this.value = value;
                this.next = next
            }
        }
        class MyLink{
            constructor(){
                this.head  = null;
                this.size = 0;
            }
            appendChild(value){
                if(this.head===null){
                    this.head = new LinkNode(value,null)
                    this.size++
                }else{
                    this.findNode(this.size).next = new LinkNode(value,null)
                    this.size++;
                }
            }
            insertNode(index,value){
                if(index===1){
                    this.head = new LinkNode(value,this.head)
                }else{
                    let pre = this.findNode(index-1)
                    pre.next = new LinkNode(value,pre.next)
                }
                this.size++
            }
            findNode(index){
                if(index < 1 || index > this.size){
                    throw new Error('索引不存在')
                }
                var current = this.head;
                for(let i = 0;i < index - 1;i++){
                    current = current.next
                }
                return current;
            }
            setNode(index,value){
                this.findNode(index).value = value
            }
            
        }
        let first = new MyLink()
        first.appendChild(5)
        first.appendChild(6)
        first.appendChild(7)
        first.insertNode(2,5.5)
        console.log(first,'链表')
        console.log(first.findNode(2))

链表实现约瑟夫环

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>
        html,body,#container{
            width:100%;
            height:100%;
        }
    </style>
</head>
<body>
    <div id="container">

    </div>
    <script>
        //[1,'2',3,8,4,5]
        //数组的变量名其实是一个地址值，指向内存中该数组的第一个元素 
        //&    具体取值时是怎么计算的呢  首地址+宽度*索引
        //链表
        //{{value:1,next:obj1}}  var obj1 = {value:3,next:obj2}
        class LinkNode{
            constructor(value,next){
                this.value = value;
                this.next = next
            }
        }
        class MyLink{
            constructor(){
                this.head  = null;
                this.tail = null;
                this.current = null;
                this.size = 0;
            }
            appendChild(value){
                if(this.head===null){
                    this.current = this.tail = this.head = new LinkNode(value,null)
                    this.size++
                }else{
                    this.tail = this.findNode(this.size).next = new LinkNode(value,this.head)
                    this.size++;
                }
            }
            insertNode(index,value){
                if(index===1){
                    this.tail.next = this.head = new LinkNode(value,this.head)
                    this.current = this.head;
                }else{
                    let pre = this.findNode(index-1)
                    pre.next = new LinkNode(value,pre.next)
                }
                this.size++
            }
            deleteNode(index){
                let temp = this.findNode(index)
                let next = temp.next
                if(index===1){
                    this.tail.next = this.head = this.head.next

                }else if(index===this.size){
                    this.tail = this.findNode(this.size-1)
                    this.tail.next = this.head
                }else{
                    let pre = this.findNode(index-1)
                    pre.next = pre.next.next
                }
                if(temp === this.current){
                    this.current = next;
                }
                this.size--
            }
            deleteNodeByValue(value){
                let index = 1;
                let current = this.head
                while(current.value!=value){
                    index++
                    if(index>this.size){
                        index = -1
                        break;
                    }
                    if(this.tail.value===current.value){
                        break;
                    }
                    current = current.next
                }
                if(index>0){
                    this.deleteNode(index)
                }
            }
            findNode(index){
                if(index < 1 || index > this.size){
                    throw new Error('索引不存在')
                }
                var current = this.head;
                for(let i = 0;i < index - 1;i++){
                    current = current.next
                }
                return current;
            }
            setNode(index,value){
                this.findNode(index).value = value
            }
            next(){
                this.current = this.current.next;
            }

        }
        let first = new MyLink()
        /*
        40个人  每9 杀一个  剩2结束
        */
        for(let i = 1;i < 41;i++){
            first.appendChild(i)
        }
        while(first.size>2){
            new Array(8).fill(0).forEach(item => {
                first.next()
            });
            first.deleteNodeByValue(first.current.value)
        }
        console.log(first,'链表')
    </script>
</body>
</html>

二叉树

增加节点与查询节点方法

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>
        html,body,#container{
            width:100%;
            height:100%;
        }
    </style>
</head>
<body>
    <div id="container">

    </div>
    <script>
        //BST   binary search tree
        class BSTNode{
            constructor(left,value,right){
                this.left = left;
                this.value = value;
                this.right = right
            }
        }
        class BSTree{
            constructor(){
                this.root = null;
                this.size = 0;
            }
            addChild(value){
                if(this.root === null){
                    this.root = new BSTNode(null,value,null)
                    this.size++
                }else{
                    this.root = this.addChildFromNode(this.root,value)
                }
            }
            addChildFromNode(node,value){
                if(value < node.value){
                    if(node.left===null){
                        node.left = new BSTNode(null,value,null)
                        this.size++
                        return node
                    }
                    node.left = this.addChildFromNode(node.left,value)
                    return node
                }else if(value > node.value){
                    if(node.right===null){
                        node.right = new BSTNode(null,value,null)
                        this.size++
                        return node
                    }
                    node.right = this.addChildFromNode(node.right,value)
                    return node
                }
            }
            hasValue(value){
                return this.hasValueFromNode(this.root,value)
            }
            hasValueFromNode(node,value){
                if(value < node.value){
                    if(node.left === null){
                        return false
                    }
                    return this.hasValueFromNode(node.left,value)
                }
                else if(value > node.value){
                    if(node.right===null){
                        return false
                    }
                    return this.hasValueFromNode(node.right,value)
                }else{
                    return true
                }
            }
        }
        let first = new BSTree();
        first.addChild(89)
        first.addChild(80)
        first.addChild(100)
        first.addChild(79)
        console.log(first.hasValue(101))
    </script>
</body>
</html>

二叉树相比数组搜索效率数量级提升

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>
        html,body,#container{
            width:100%;
            height:100%;
        }
    </style>
</head>
<body>
    <div id="container">

    </div>
    <script>
        //BST   binary search tree
        class BSTNode{
            constructor(left,value,right){
                this.left = left;
                this.value = value;
                this.right = right
            }
        }
        class BSTree{
            constructor(){
                this.root = null;
                this.size = 0;
            }
            addChild(value){
                if(this.root === null){
                    this.root = new BSTNode(null,value,null)
                    this.size++
                }else{
                    this.root = this.addChildFromNode(this.root,value)
                }
            }
            addChildFromNode(node,value){
                if(value < node.value){
                    if(node.left===null){
                        node.left = new BSTNode(null,value,null)
                        this.size++
                        return node
                    }
                    node.left = this.addChildFromNode(node.left,value)
                    return node
                }else if(value > node.value){
                    if(node.right===null){
                        node.right = new BSTNode(null,value,null)
                        this.size++
                        return node
                    }
                    node.right = this.addChildFromNode(node.right,value)
                    return node
                }
            }
            hasValue(value){
                return this.hasValueFromNode(this.root,value)
            }
            hasValueFromNode(node,value){
                if(value < node.value){
                    if(node.left === null){
                        return false
                    }
                    return this.hasValueFromNode(node.left,value)
                }
                else if(value > node.value){
                    if(node.right===null){
                        return false
                    }
                    return this.hasValueFromNode(node.right,value)
                }else{
                    return true
                }
            }
        }
        let first = new BSTree();
        let result = []
        while(result.length<10000){
            let number = Math.floor(Math.random()*100000)
            if(result.indexOf(number)<0){
                result.push(number)
            }
        }
        result.forEach((item)=>{
            first.addChild(item)
        })

        let start1 = new Date().getTime()
        for(let j = 0;j < 10000;j++){
            let number = Math.floor(Math.random()*100000)
            for(let i = 0;i < result.length;i++){
                if(number===result[i]){
                    break;
                }
            }
        }
        let end1 = new Date().getTime()


        let start2 = new Date().getTime()
        for(let j = 0;j < 10000;j++){
            let number = Math.floor(Math.random()*100000)
            first.hasValue(number)
        }
        let end2 = new Date().getTime()

        console.log(end1-start1)
        console.log(end2-start2)
        // first.addChild(89)
        // first.addChild(80)
        // first.addChild(100)
        // first.addChild(79)
        // console.log(first.hasValue(101))
    </script>
</body>
</html>

二叉树的删除方法

删除节点100前
删除节点100后

代码：

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>
        html,body,#container{
            width:100%;
            height:100%;
        }
    </style>
</head>
<body>
    <div id="container">

    </div>
    <script>
        //BST   binary search tree
        class BSTNode{
            constructor(left,value,right){
                this.left = left;
                this.value = value;
                this.right = right
            }
        }
        class BSTree{
            constructor(){
                this.root = null;
                this.size = 0;
            }
            addChild(value){
                if(this.root === null){
                    this.root = new BSTNode(null,value,null)
                    this.size++
                }else{
                    this.root = this.addChildFromNode(this.root,value)
                }
            }
            addChildFromNode(node,value){
                if(value < node.value){
                    if(node.left===null){
                        node.left = new BSTNode(null,value,null)
                        this.size++
                        return node
                    }
                    node.left = this.addChildFromNode(node.left,value)
                    return node
                }else if(value > node.value){
                    if(node.right===null){
                        node.right = new BSTNode(null,value,null)
                        this.size++
                        return node
                    }
                    node.right = this.addChildFromNode(node.right,value)
                    return node
                }
            }
            deleteValue(value){
                this.root = this.deleteFromNode(this.root,value)
            }
            deleteFromNode(node,value){
                if(value < node.value){
                    node.left = this.deleteFromNode(node.left,value)
                    return node
                }else if(value > node.value){
                    node.right = this.deleteFromNode(node.right,value)
                }else if(value === node.value){
                    //该节点为叶子节点
                    if(node.left===null&&node.right===null){
                        this.size--
                        return null
                    }
                    //只有左节点
                    if(node.left!=null&&node.right===null){
                        this.size--
                        return node.left
                    }
                    //只有右节点
                    if(node.left===null&&node.right!=null){
                        this.size--
                        return node.right
                    }
                    
                    //有两个子节点
                    if(node.left!=null && node.right!=null){
                        let minNode = this.getMinFromNode(node.right)
                        node.value = minNode.value
                        node.right = this.deleteFromNode(node.right,minNode.value)
                        return node;
                    }
                }
                return node
            }
            hasValue(value){
                return this.hasValueFromNode(this.root,value)
            }
            hasValueFromNode(node,value){
                if(value < node.value){
                    if(node.left === null){
                        return false
                    }
                    return this.hasValueFromNode(node.left,value)
                }
                else if(value > node.value){
                    if(node.right===null){
                        return false
                    }
                    return this.hasValueFromNode(node.right,value)
                }else{
                    return true
                }
            }
            getMin(){
                return this.getMinFromNode(this.root)
            }
            getMinFromNode(node){
                if(node.left===null){
                    return node
                }else{
                    return this.getMinFromNode(node.left)
                }
            }
        }
        let first = new BSTree();
        first.addChild(89)
        first.addChild(80)
        first.addChild(100)
        first.addChild(79)
        first.addChild(95)
        first.addChild(120)
        first.addChild(91)
        first.addChild(101)
        first.addChild(121)
        first.deleteValue(100)
        console.log(first)
    </script>
</body>
</html>

二叉树的前中后序遍历层级遍历深度获取

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>
        html,body,#container{
            width:100%;
            height:100%;
        }
    </style>
</head>
<body>
    <div id="container">

    </div>
    <script>
        class MyQueue{
            constructor(){
                this.container = []
            }
            enQueue(value){//入队
                this.container.push(value)
            }
            deQueue(){
                return this.container.shift()
            }
            size(){
                return this.container.length
            }
        }
        //BST   binary search tree
        class BSTNode{
            constructor(left,value,right){
                this.left = left;
                this.value = value;
                this.right = right
            }
        }
        class BSTree{
            constructor(){
                this.root = null;
                this.size = 0;
            }
            addChild(value){
                if(this.root === null){
                    this.root = new BSTNode(null,value,null)
                    this.size++
                }else{
                    this.root = this.addChildFromNode(this.root,value)
                }
            }
            addChildFromNode(node,value){
                if(value < node.value){
                    if(node.left===null){
                        node.left = new BSTNode(null,value,null)
                        this.size++
                        return node
                    }
                    node.left = this.addChildFromNode(node.left,value)
                    return node
                }else if(value > node.value){
                    if(node.right===null){
                        node.right = new BSTNode(null,value,null)
                        this.size++
                        return node
                    }
                    node.right = this.addChildFromNode(node.right,value)
                    return node
                }
            }
            deleteValue(value){
                this.root = this.deleteFromNode(this.root,value)
            }
            deleteFromNode(node,value){
                if(value < node.value){
                    node.left = this.deleteFromNode(node.left,value)
                    return node
                }else if(value > node.value){
                    node.right = this.deleteFromNode(node.right,value)
                }else if(value === node.value){
                    //该节点为叶子节点
                    if(node.left===null&&node.right===null){
                        this.size--
                        return null
                    }
                    //只有左节点
                    if(node.left!=null&&node.right===null){
                        this.size--
                        return node.left
                    }
                    //只有右节点
                    if(node.left===null&&node.right!=null){
                        this.size--
                        return node.right
                    }
                    
                    //有两个子节点
                    if(node.left!=null && node.right!=null){
                        let minNode = this.getMinFromNode(node.right)
                        node.value = minNode.value
                        node.right = this.deleteFromNode(node.right,minNode.value)
                        return node;
                    }
                }
                return node
            }
            hasValue(value){
                return this.hasValueFromNode(this.root,value)
            }
            hasValueFromNode(node,value){
                if(value < node.value){
                    if(node.left === null){
                        return false
                    }
                    return this.hasValueFromNode(node.left,value)
                }
                else if(value > node.value){
                    if(node.right===null){
                        return false
                    }
                    return this.hasValueFromNode(node.right,value)
                }else{
                    return true
                }
            }
            getMin(){//寻找最小值
                return this.getMinFromNode(this.root)
            }
            getMinFromNode(node){
                if(node.left===null){
                    return node
                }else{
                    return this.getMinFromNode(node.left)
                }
            }
            getMax(){//寻找最大值
                return this.getMaxFromNode(this.root)
            }
            getMaxFromNode(node){
                if(node.right===null){
                    return node
                }else{
                    return this.getMaxFromNode(node.right)
                }
            }
            getDep(){//求二叉树的深度（即层数）
                return this.getDepFromNode(this.root)
            }
            getDepFromNode(node){
                let left;
                if(node.left===null){
                    left = 0
                }else{
                    left = this.getDepFromNode(node.left)
                }
                let right;
                if(node.right===null){
                    right = 0
                }else{
                    right = this.getDepFromNode(node.right)
                }
                return Math.max(left,right)+1
            }
            preErgodic(fn){//前序遍历
                this.preErgodicFromNode(this.root,fn)
            }
            preErgodicFromNode(node,fn){
                fn(node)
                if(node.left){
                    this.preErgodicFromNode(node.left,fn)
                }
                if(node.right){
                    this.preErgodicFromNode(node.right,fn)
                }
            }
            midErgodic(fn){//中序遍历
                this.midErgodicFromNode(this.root,fn)
            }
            midErgodicFromNode(node,fn){
                if(node.left){
                    this.midErgodicFromNode(node.left,fn)
                }
                fn(node)
                if(node.right){
                    this.midErgodicFromNode(node.right,fn)
                }
            }
            nextErgodic(fn){//中序遍历
                this.nextErgodicFromNode(this.root,fn)
            }
            nextErgodicFromNode(node,fn){
                if(node.left){
                    this.nextErgodicFromNode(node.left,fn)
                }
                if(node.right){
                    this.nextErgodicFromNode(node.right,fn)
                }
                fn(node)
            }
            storeyErgodic(fn){
                let myQueue = new MyQueue()
                myQueue.enQueue(this.root)
                let tmp;
                while(myQueue.size()>0){
                    tmp = myQueue.deQueue()
                    fn(tmp)
                    if(tmp.left){
                        myQueue.enQueue(tmp.left)
                    }
                    if(tmp.right){
                        myQueue.enQueue(tmp.right)
                    }
                }
            }
        }
        let first = new BSTree();
        first.addChild(89)
        first.addChild(80)
        first.addChild(100)
        first.addChild(79)
        first.addChild(95)
        first.addChild(120)
        first.addChild(91)
        first.addChild(101)
        first.addChild(121)
       first.deleteValue(100)
        //console.log(first.getDep())
        first.preErgodic((node)=>{
            console.log(node.value)
        })
        console.log('----------------------------------------------')
        first.midErgodic((node)=>{
            console.log(node.value)
        })
        console.log('----------------------------------------------')
        first.nextErgodic((node)=>{
            console.log(node.value)
        })
        console.log('----------------------------------------------')
        first.storeyErgodic((node)=>{
            console.log(node.value)
        })
    </script>
</body>
</html>

相关文章

网友评论

      本文标题：js数据结构和算法

      本文链接：https://www.haomeiwen.com/subject/hxwmbltx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|js数据结构和算法|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！