精华内容
下载资源
问答
  • 本文就来详细讲解一下双向链表的概念以及如何实现一个双向链表。 公众号:Lpyexplore的编程小屋 关注我,每天更新,带你在python爬虫的过程中学习前端,还有更多电子书和面试题等你来拿 数据结构——双向链表一、...

    本系列文章【数据结构与算法】所有完整代码已上传 github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接

    上一篇文章讲解了链表的相关知识,并用代码实现了一个链表结构。那么本文将介绍一下另一种特殊的链表结构,叫做 双向链表。 顾名思义,普通的链表都是从 head 开始往后遍历结构内的元素,那么双向链表就是既可以从头开始遍历,又可以从结构的末尾开始遍历。

    上一篇文章的跳转链接——【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构

    本文就来详细讲解一下双向链表的概念以及如何实现一个双向链表。

    • 公众号:前端印象
    • 不定时有送书活动,记得关注~
    • 关注后回复对应文字领取:【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

    在这里插入图片描述

    一、什么是双向链表

    在上一篇文章中,我们用一个生活中的例子来解释了链表的概念,那么本文就延用这个例子,并对该例子做一些改动,来解释什么是 双向链表

    我们来看一下这个例子:

    在一个教室里,所有的课桌排成一列,如图
    在这里插入图片描述
    相信在你们的读书生涯中,老师肯定有要求你们记住自己的前后桌是谁。所以该例子中,老师就要求学生们记住自己的前后桌,其中坐在第一排的学生需要记住自己是第一排的学生以及自己的后桌是谁;最后一排的学生要记住自己的前桌是谁以及自己是最后一排的学生。如图:
    在这里插入图片描述
    这一列座位就相当于一个 双向链表。

    假如有一天,老师还没记住每个学生的名字,于是就问:这一列第三个人叫什么名字?这时就要从第一个学生开始数,例如从图中坐在第一个的 小5 开始数:第一个人是 小5,他的后桌是 小7;因此第二个人就是 小7,他的后桌是 小1;因此第三个人就是 小1 了。此时老师问 小1:你的前桌叫什么名字?你的后桌叫什么名字?

    因为刚开始老师就让每个学生记住了自己的前桌以及后桌,所以此时 小1 能很快地告诉老师他的前桌是 小7,他的后桌是 小6

    但是,我们设想一下,如果是上一篇文章的 链表结构 的例子中,如果老师在得知了第三个人是 小1 以后,询问 小1 的前桌叫什么名字,小1 能回答上来吗?并不能,因为老师只让每个学生记住了自己的后桌,所以此时想要得知 小1 的前桌叫什么名字,只能这样:第三个学生叫 小1,那么他的前桌就坐在第二个位置,所以从第一个学生开始数,第一个学生是 小5,他的后桌是 小7;因此第二个学生就是 小7。当然本文举得例子中学生数量有点少,但一旦数量多起来了,每次问一个学生他的前桌叫什么名字的时候,都要从头开始数。

    从中可以看出,让每个学生记住自己的前桌后桌是非常有必要的,因为在某些情况下,可以快速地解决问题。

    上面讲了那么多,接下来我们就来看一下 双向链表 是什么样的,如图
    在这里插入图片描述
    可以看到,对比 链表结构双向链表 多了一个指针 tail,它是指向最后一个元素的,就相当于例子中的学生记住了自己是最后一排。

    二、双向链表的方法

    因为 双向链表 是链表的一种特殊形式,所以这两者的常用方法也是一样的,只不过实现方式不一样,那么我再列举一下有哪些常用方法吧,如下表

    方法含义
    append()向双向链表尾部追加元素
    insert()在双向链表的某个位置插入元素
    get()获取双向链表对应位置的元素
    indexOf()获取某元素在双向链表中的索引
    update()修改双向链表中某个位置上的元素的值
    removeAt()移除双向链表中某位置上的某元素
    remove()移除双向链表中的某元素
    isEmpty()判断双向链表内是否为空
    size()返回双向链表内元素个数
    toString()以字符串的形式展示双向链表内的所有元素

    接下来就用 JavaScript 来实现一下以上这些方法

    三、用代码实现双向链表

    (1)创建一个构造函数

    首先创建一个大的构造函数,用于存放双向链表的一些属性和方法。

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    }
    

    其中,属性 head 表示双向链表中的第一个元素;属性 tail 表示双向链表中的最后一个元素

    (2)创建内部构造函数

    双向链表的每一个元素都有三个属性,即previtemnext,分别表示该元素的前一个元素是谁 、存储着该元素的值和该元素的后一个元素是谁。所以我们就在双向链表的构造函数内部创建一个内部构造函数用于之后创建元素的实例对象

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    }
    

    (3)实现append()方法

    append()方法就是将元素添加到双向链表的末尾。

    实现思路:

    1. 先创建新元素的实例对象 node
    2. 先判断双向链表内有无元素,若没有元素,则将属性 head 和 属性 tail 都指向 node,最后属性 length + 1
    3. 若双向链表中有元素了,则因为双向链表内多了一个指针 tail,所以我们要实现 append()方法也就方便了很多,只需要将 tail 指向 node,然后将原本的末尾元素 old_nodenext 指向 node,并将 nodeprev属性指向 old_node即可,然后属性 length + 1

    为了方便大家理解,我用一个动图来向大家演示一下:
    在这里插入图片描述
    在这里插入图片描述

    思路讲解完了,我们来实现一下该方法

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//在末尾加入元素
        DoubleLinkedList.prototype.append = function (item) {
        	// 1.创建新元素的实例对象
            let node = new Node(item)
    		
    		// 2.判断双向链表内是否有元素
            if(this.length === 0) {
                this.head = node
                this.tail = node
            }
            else {
                node.prev = this.tail
                this.tail.next = node
                this.tail = node
            }
    		
    		// 3. 双向链表内元素 + 1
            this.length ++
        }
    }
    

    接下里我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.append('js')
    dl.append('python')
    

    此时的链表内是这样的
    在这里插入图片描述

    (4)实现insert()方法

    insert()方法就是在指定的索引位置插入元素。一共需要传入两个参数,第一个是 position,表示需要插入元素的位置;第二个参数是 item,表示元素的值

    实现思路:

    1. 创建新的元素实例对象 node
    2. 判断指定的索引位置 position 是否越界,即是否小于0,或者大于双向链表的长度。若越界了,则直接返回false
    3. 判断 position 是否为0。若为0,则直接将双向链表原本的第一个元素 ,也就是 head所对应的元素 old_node 赋值给 nodenext属性,再将 node 赋值给 old_nodeprev 属性,然后将 node赋值给 head,表示现在链表的第一个元素为 node
    4. position 不为0,则遍历双向链表,同时记录遍历的索引 index 、遍历的上一个元素 prev 和在 index索引位置上的元素 current,当 index == position时,将 node赋值给 prevnext属性,将 current 赋值给 nodenext属性,再将 prev 赋值给 nodeprev 属性,最后将 node 赋值给 currentprev 属性
    5. 属性 length + 1

    为了方便大家理解,我用一个动图来向大家演示一下:
    在这里插入图片描述
    在这里插入图片描述
    看完了方法的实现思路,我们来用代码实现一下该方法

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//向指定位置插入元素
        DoubleLinkedList.prototype.insert = function (position, item) {
            // 1.判断是否越界
            if(position < 0 || position > this.length) {
                return false
            }
            // 2.创建新元素的实例对象
            let node = new Node(item)
            let index = 0
            let current = this.head
            let prev = null
            
            // 3.判断插入位置是否等于元素个数
            if(position === this.length) {
            	//当 position 与 length相等时,就相当于在末尾添加元素
                this.append(item)
            }
    
    		// 4. 判断元素是否添加到第一个位置
            else if(position === 0) {
                node.next = this.head
                this.head.prev = node
                this.head = node
                this.length ++
            }
            else {
            	// 5.遍历链表,直到找到position位置上的元素
                while (index < position) {
                    prev = current
                    current = current.next
                    index ++
                }
                // 6.插入新元素
                prev.next = node
                current.prev = node
                node.prev = prev
                node.next = current
                this.length ++
            }
        }
    }
    

    接下来我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.insert(0, 'C++')
    

    此时的双向链表是这样的
    在这里插入图片描述
    在执行一次 insert()方法

    di.append('js')              //在末尾添加元素 js
    dl.insert(1, 'python')       //在索引 1处插入元素python
    

    此时的双向链表是这样的
    在这里插入图片描述
    最后我们再向索引为 3 的位置插入元素 java,因为此时 length = 3,即双向链表元素个数为 3,这就相当于在末尾添加元素

    dl.insert(3, 'java')
    

    所以此时的链表是这样的
    在这里插入图片描述

    (5)实现get()方法

    get()方法就是获取对应位置上的元素。需要传入一个参数,即 position,表示需要获取元素的索引

    实现思路:

    1. 判断 position 是否越界。若越界,则直接返回false
    2. 遍历链表,同时记录当前索引 index,当 index == position时,返回当前位置上的元素

    该方法思路比较简单,几乎跟链表的 get()方法一样,我们来看一下

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//获取对应位置上的元素
        DoubleLinkedList.prototype.get = function (position) {
            if(position < 0 || position > this.length - 1) {
                return false
            }
            let index = 0
            let current = this.head
            while (index < position) {
                current = current.next
                index ++
            }
            return current.item
        }
    }
    

    我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.append('C++')
    dl.append('js')
    dl.append('python')
    
    dl.get(-2)           //返回 false
    dl.get(0)            //返回 C++
    dl.get(2)            //返回 python
    dl.get(3)            //返回 false
    

    (6)实现indexOf()方法

    indexOf()方法就跟数组的一样,获取某元素在双向链表中的索引值,若双向链表中不存在该元素,则返回 -1

    这个方法思路很简单,就不详细讲解了,直接来看代码

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//获取元素的索引
        DoubleLinkedList.prototype.indexOf = function (item) {
            let current = this.head
            let index = 0
            
            // 1.遍历双向链表
            while (index < this.length) {
            	// 2. 找到对应元素,返回索引值
                if(current.item === item) {
                    return index
                }
                else {
                    index ++
                    current = current.next
                }
            }
            // 3.未找到对应元素,返回 -1
            return -1
    
        }
    }
    

    我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.append('C++')
    dl.append('js')
    dl.append('python')
    
    dl.indexOf('C++')           //返回 0
    dl.indexOf('js')            //返回 1
    dl.indexOf('python')        //返回 2
    dl.indexOf('java')          //返回 -1
    

    (7)实现update()方法

    update()方法就是用于修改双向链表中某位置上的元素的值。因此该方法需要传入两个参数,第一个参数是 position,表示需要修改的元素的索引;第二个参数是 NewItem,表示修改后的值

    该方法的实现思路跟普通链表一模一样,所以就不讲解具体的实现思路了,直接来看代码吧

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//修改某位置上的元素
        DoubleLinkedList.prototype.update = function (position, item) {
        	
        	// 1.判断是否越界
            if(position < 0 || position >= this.length) {
                return false
            }
            let index = 0
            let current = this.head
            
            // 2.遍历双向链表,直到找到对应位置上的元素
            while (index < position) {
                index ++
                current = current.next
            }
            // 3.修改position索引位置上的元素的值
            current.item = item
            return true
        }
    }
    

    我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.append('C++')
    dl.append('js')
    dl.append('python')
    

    此时的链表是这样的
    在这里插入图片描述
    现在调用一下 update()方法,修改索引位置为 2 的元素的值

    dl.update(2, 'java')
    

    此时的链表是这样的
    在这里插入图片描述

    (8)实现removeAt()方法

    removeAt()方法就是用于移除双向链表中某位置上的某元素。该方法只需要传入一个参数 position,表示需要移除元素的索引

    实现思路:

    1. 先判断 position 是否越界,若越界了,则直接返回 false 表示移除元素失败
    2. 若没有越界,则判断 position 是否为 0,若等于 0,则直接将第一个链表的 next 值赋值给 head,然后 length - 1
    3. position 不等于 0而等于 length - 1,则将末尾元素的前一个元素,即 tailprev对应的元素的 next 属性设置成 null,并将 tail 指向当前 tailprev,最后 length - 1
    4. position 既不等于 0,又不等于 length - 1,则遍历双向链表,同时记录当前索引 index,遍历的当前元素 currentcurrent的上一个元素 prev
    5. index === position时,将 current 的下一个元素,即 currentnext 属性值赋值给 prevnext 属性,同时将 current 的下一个元素的 prevprev 属性设置成 prev,最后 length - 1

    为了让大家更好地理解该方法的实现思路,我制作了一个动图来帮助大家理解,如图
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    思路讲完了,我们直接来看代码

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//移除某位置上的元素
        DoubleLinkedList.prototype.removeAt = function (position) {
            // 1.判断是否越界
            if(position < 0 || position >= this.length) {
                return false
            }
            
            // 2.判断清除的元素是否为链表的唯一元素
            if(position === 0 && position === this.length - 1) {
                this.head = null
                this.tail = null
            }
            // 3.判断清除的元素是否为链表的第一个元素
            else if(position === 0) {
                this.head.next.prev = null
                this.head = this.head.next
            }
            // 4.判断清除的元素是否为链表的最后一个元素
            else if(position === this.length - 1) {
                this.tail.prev.next = null
                this.tail = this.tail.prev
            }
            else {
                let current = this.head
                let prev = null
                let index = 0
                // 5.遍历双向链表
                while (index < position) {
                    index ++
                    prev = current
                    current = current.next
                }
                // 6.删除对应位置上的元素
                prev.next = current.next
                current.next.prev = prev
            }
            // 7.元素个数 - 1
            this.length --
            return true
    
        }
    }
    

    我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.append('C++')
    dl.append('js')
    dl.append('python')
    
    dl.removeAt(2)         //删除索引为 2位置上的元素
    

    此时的双向链表是这样的
    在这里插入图片描述

    (9)实现remove()方法

    remove()方法就是用于移除双向链表链表中的某元素,并返回被删除元素所在的索引位置,若链表中没有对应元素,则返回 false 。该方法需要传入一个参数 data用于查找链表中对应的元素

    实现思路:

    1. 利用上面封装的 indexOf()方法,将 data 作为参数传入,获取到 data 在链表中的索引 index
    2. 再利用上面封装的 removeAt()方法,将 index 作为参数传入,就可以实现 remove()方法的功能了。

    我们简单来写一下代码实现该方法

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//移除某元素
        DoubleLinkedList.prototype.remove = function (data) {
        	// 1.获取data在双向链表中的索引
            let index = this.indexOf(data)
    		
    		// 2.利用removeAt()方法删除双向链表中的data
            this.removeAt(index)
            
            // 3.返回被删除元素data在双向链表中的索引
            return index
        }
    }
    

    我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.append('C++')
    dl.append('js')
    dl.append('python')
    
    dl.remove('js')            //返回 1,此时length = 2
    dl.remove('python')        //返回 1,此时length = 1
    

    此时的链表是这样的
    在这里插入图片描述

    (10)实现isEmpty()方法

    isEmpty()方法就是判断双向链表中是否有元素。若有元素,则返回 false;反之,返回 true

    该方法的实现思路很简单,直接判断属性 length 是否等于 0 就可以了。

    话不多说,我们赶紧写代码实现一下该方法

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//判断双向链表是否为空
        DoubleLinkedList.prototype.isEmpty = function () {
            if(this.length === 0) {
                return true
            }
            else {
                return false
            }
        }
    }
    

    我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.isEmpty()             //返回 true,此时双向链表中无元素
    
    dl.append('C++')
    dl.append('js')
    dl.append('python')
    
    dl.isEmpty()             //返回 false,此时双向链表中有3个元素
    

    (11)实现size()方法

    szie()方法就是返回链表内的元素个数

    我们来实现一下该方法

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//返回双向链表元素个数
        DoubleLinkedList.prototype.size = function () {
            return this.length
        }
    }
    

    我们来使用一下该方法

    let dl = new DoubleLinkedList()
    
    dl.size()             //返回 0,此时双向链表中无元素
    
    dl.append('C++')
    dl.append('js')
    dl.append('python')
    
    dl.size()             //返回 3,此时双向链表中有3个元素
    

    (12)实现toString()方法

    toString()方法就是以字符串的形式展示双向链表内的所有元素

    实现思路很简单,就是遍历双向链表中的每一个元素,并将每个元素以字符串的形式连接起来即可

    我们来实现一下该方法

    function DoubleLinkedList() {
        //属性
        this.head = null
        this.tail = null
        this.length = 0
    
    	//元素的构造函数
        function Node(item) {
            this.item = item
            this.next = null
            this.prev = null
        }
    
    	//展示双向链表数据
        DoubleLinkedList.prototype.toString = function () {
            let current = this.head
            let string = ''
            while (current) {
                string += current.item + ' '
                current = current.next
            }
            return string
        }
    }
    

    四、双向链表的补充

    其实平常的时候 双向链表 的应用场景比较多,而且它某些时候比普通的链表数据操作的效率要高。

    例如:假设有一个 length = 9999 的普通链表,我们要删除该链表索引为 9997 的元素,那么我们只能从链表的第一个元素,即从 head 指向的元素开始遍历链表,直到找到索引为 9997 的元素,一共要遍历9998次,这样效率是非常低的。

    那么如果把普通链表换成双向链表呢?当我们得知要删除索引为 9997 的元素时,我们可以先计算 99979999 - 1 = 9998 的差值 、99970 的差值,若前者差值小,则可以从双向链表的 tail 指向的元素往前遍历;反之,从 head 指向的元素往后遍历。如图
    在这里插入图片描述

    五、总结

    双向链表的讲解就到这里了,希望大家对双向链表有了更深一层的理解。下一篇文章我将讲解一下哈希表

    大家可以关注我,之后我还会一直更新别的数据结构与算法的文章来供大家学习,并且我会把这些文章放到【数据结构与算法】这个专栏里,供大家学习使用。

    然后大家可以关注一下我的微信公众号:前端印象,等这个专栏的文章完结以后,我会把每种数据结构和算法的笔记放到公众号上,大家可以去那获取。

    或者也可以去我的github上获取完整代码,欢迎大家点个Star

    我是Lpyexplore,创作不易,喜欢的加个关注,点个收藏,给个赞~ 带你们在Python爬虫的过程中学习Web前端

    展开全文
  • [js] 请使用 js 实现一个双向链表

    多人点赞 2021-01-03 10:28:13
    [js] 请使用 js 实现一个双向链表 链表结构是我们在面试中经常会被问起的较为基础的数据结构问题,起初学习数据结构使用的是C++语言,最近在做前端面试题的过程中没碰到了需要用js实现双链表的需求,百度出来的文章...

    [js] 请使用 js 实现一个双向链表

    链表结构是我们在面试中经常会被问起的较为基础的数据结构问题,起初学习数据结构使用的是C++语言,最近在做前端面试题的过程中没碰到了需要用js实现双链表的需求,百度出来的文章发现可很多错误,于是索性自己重新写了,并且列出了一些错误点,这里给大家较为详细的一步步看一下实现思想和步骤,相较于C++语言,js的实现可以说是很简单了,不需要创建繁琐的对象,更加直观易懂;
    首先我们来看一下双向链表的结构图:
    在这里插入图片描述
    每个结点包含三部分,指向前一个结点的指针(pre),指向后一个节点的指针(next),以及自己的数据部分(element),于是我们就可以先写出结点对象

    function Node:定义结点对象

    function Node(element) {
      this.element = element
      this.next = null
      this.previous = null
    }
    

    然后我们开始实现插入链表的算法
    在这里插入图片描述

    (声明)下面函数中的this是我们最后初始化链表的实例,这里大家不要疑惑。可以拉到最下面我们初始化链表那里,相信你会明白呦

    **`function insert`:插入节点**
    
    function insert(newelement, currentelement) {
      var newNode = new Node(newelement)
      var currentNode = this.find(currentelement)
      if (currentNode === 'error') {
        console.log('无法插入,要插入节点不存在')
        return
      }
      if (currentNode.next != null) {
        newNode.next = currentNode.next
        currentNode.next = newNode
        newNode.previous = currentNode
        newNode.next.previous = newNode
      } else {
        currentNode.next = newNode
        newNode.previous = currentNode
      }
    }
    

    function find:找到插入位置

    function find(element) {
      var currentNode = this.head
      while (currentNode.element != element) {
      /*如果找到最后一个节点还没有找到我们的插入点,那么我们就会返回错误*/
        if (currentNode.next == null) {
          console.log('can not find this node; maybe not have this node')
          return 'error'
        }
        currentNode = currentNode.next
      }
      return currentNode
    }
    

    接下来是移除结点的实现,如果看懂了插入节点的实现,那么移除就会很简单了,相信大家都可以很快明白,这里就直接贴出实现代码;

    function remove:移除一个结点
    
    function remove(element) {
      var currentNode = this.find(element)
      if (currentNode === 'error') {
        console.log('要移除节点不存在')
        return
      }
      /*首先是不是头尾节点的情况*/
    
      if (currentNode.next != null && currentNode.previous != null) {
        currentNode.previous.next = currentNode.next
        currentNode.next.previous = currentNode.previous
        currentNode.next = null
        currentNode.previous = null
      } else if (currentNode.previous == null) {
        /*当是头节点的时候*/
        this.head = currentNode.next
        currentNode.next.previous = null
        currentNode.next = null
      } else if (currentNode.next == null) {
        /*当是尾节点的时候 */
    
        currentNode.previous.next = null
        currentNode.previous = null
      }
    }
    
    

    截止到这里我们基本功能已经有了,下面使我们根据自己需要可以自定义一些其他函数

    function lastNode:找到最后一个节点
    
    function lastNode() {
      var head = this.head
      while (head.next != null) {
        head = head.next
      }
      return head     //这里head在尾节点的位置
    }
    
    function append:将要添加的结点放在链表末尾
    
    function append(element) {
      var lastnode = this.lastNode()
      var newNode = new Node(element)
      lastnode.next = newNode
      newNode.previous = lastnode
    }
    
    function showlist:将链表所有的结点打印出来
    
    function showlist() {
      var head = this.head
      do {
        console.log(head.element)
        head = head.next
      } while (head != null)
      // 大家可以看一下下面注释内容存在什么问题,留给大家思考一下
      // while (head.next != null) {
      //   console.log(head.element)
      //   head = head.next
      // }
    }
    

    接下来是对链表进行初始化,这也是上述函数中所有this所代表的实例

    function initlist:初始化链表,并将所有方法注册到链表中

    function initlist() {
      this.head = new Node('one')
      this.find = find
      this.insert = insert
      this.remove = remove
      this.showlist = showlist
      this.lastNode = lastNode
      this.append = append
    }
    
    var list = new initlist()
    list.insert('two', 'one')
    list.insert('four', 'two')
    list.insert('three', 'two')
    
    // console.log(list.head.next)
    list.showlist()
    list.append('A')
    list.append('B')
    list.insert('B2', 'B')
    list.showlist()
    console.log(list.lastNode())
    // list.remove('one')
    // list.showlist()
    console.log(list.find('A').previous)
    // console.log(list.find('four').previous)
    // console.log(list.head.element)
    
    

    下面是运行结果:
    在这里插入图片描述
    源码:

    function Node(element) {
      this.element = element
      this.next = null
      this.previous = null
    }
    function find(element) {
      var currentNode = this.head
      while (currentNode.element != element) {
        if (currentNode.next == null) {
          console.log('can not find this node; maybe not have this node')
          return 'error'
        }
        currentNode = currentNode.next
      }
      return currentNode
    }
    function insert(newelement, currentelement) {
      var newNode = new Node(newelement)
      var currentNode = this.find(currentelement)
      if (currentNode === 'error') {
        console.log('无法插入,要插入节点不存在')
        return
      }
      if (currentNode.next != null) {
        newNode.next = currentNode.next
        currentNode.next = newNode
        newNode.previous = currentNode
        newNode.next.previous = newNode
      } else {
        currentNode.next = newNode
        newNode.previous = currentNode
      }
    }
    function remove(element) {
      var currentNode = this.find(element)
      if (currentNode === 'error') {
        console.log('要移除节点不存在')
        return
      }
      /*首先是不是头尾节点的情况*/
    
      if (currentNode.next != null && currentNode.previous != null) {
        currentNode.previous.next = currentNode.next
        currentNode.next.previous = currentNode.previous
        currentNode.next = null
        currentNode.previous = null
      } else if (currentNode.previous == null) {
        /*当是头节点的时候*/
        this.head = currentNode.next
        currentNode.next.previous = null
        currentNode.next = null
      } else if (currentNode.next == null) {
        /*当是尾节点的时候 */
    
        currentNode.previous.next = null
        currentNode.previous = null
      }
    }
    function showlist() {
      var head = this.head
      do {
        console.log(head.element)
        head = head.next
      } while (head != null)
      // while (head.next != null) {
      //   console.log(head.element)
      //   head = head.next
      // }
    }
    function initlist() {
      this.head = new Node('one')
      this.find = find
      this.insert = insert
      this.remove = remove
      this.showlist = showlist
      this.lastNode = lastNode
      this.append = append
    }
    function append(element) {
      var lastnode = this.lastNode()
      var newNode = new Node(element)
      lastnode.next = newNode
      newNode.previous = lastnode
    }
    function lastNode() {
      var head = this.head
      while (head.next != null) {
        head = head.next
      }
      return head
    }
    var list = new initlist()
    list.insert('two', 'one')
    list.insert('four', 'two')
    list.insert('three', 'two')
    
    // console.log(list.head.next)
    list.showlist()
    list.append('A')
    list.append('B')
    list.insert('B2', 'B')
    list.showlist()
    console.log(list.lastNode())
    // list.remove('one')
    // list.showlist()
    console.log(list.find('A').previous)
    // console.log(list.find('four').previous)
    // console.log(list.head.element)
    
    

    个人简介

    我是歌谣,欢迎和大家一起交流前后端知识。放弃很容易,
    但坚持一定很酷。欢迎大家一起讨论

    主目录

    与歌谣一起通关前端面试题

    展开全文
  • 点击上方“3D视觉工坊”,选择“星标”干货第时间送达标题:CoBigICP: Robust and Precise Point Set Registration using Corren...

    点击上方“3D视觉工坊”,选择“星标”

    干货第一时间送达

    标题:CoBigICP: Robust and Precise Point Set Registration using Correntropy Metrics and Bidirectional Correspondence

    作者:Pengyu Yin, Di Wang, Shaoyi Du, Shihui Ying, Yue Gao, and Nanning Zheng, Xi’an Jiaotong University

    来源:IROS 2020

    编译:曹明

    审核:lionheart

    摘要

    在这篇文章中,我们提出了一个全新的ICP(Iterative Closest Point)、基于概率的变体,称之为CoBigICP。这个方法充分利用了点云的局部几何特性以及点云的全局噪声特性。从局部范围看,该方法的目标函数通过双向匹配,集成了源点云(source point cloud)与目标点云(target  point cloud)的三维结构特征;全局范围来看,该方法引入了相关熵(correntropy)的误差度量来作为噪声模型,以排除外点。这篇文章还展示了正态分布变换(Normal distributions transform, NDT)与相关熵的紧密相似性。为了简化优化过程,我们还提出了一种在特殊欧式群上的流形上的参数化方法。一系列实验表明了CoBigICP比目前最先进的方法要好。

    主要贡献

    1.     本文提出的算法利用了双向匹配的方法来构建一个对称模型。

    2.     利用相关熵来作为一个鲁棒的误差度量,并证明了其有效性。我们还展示了NDT与相关熵的相似性。

    3.     本文提出了一种基于流形上的参数化方法来求解该问题。

    方法概览

    A.双向匹配

    在传统的ICP匹配问题中,给定源点云,则会从目标点云中寻找与源点云里每个点ai最近的一个点bcf(i),作为源点云的匹配,其公式表达为:

    其中,T为源点云与目标点云的三维变换。如此,便找到了一个目标点云的子集bcf,以及一个映射

    而在本文的的方法中,还进行了一次反向的查找。即对上述点集bcf中的每一个点,去寻找源点云里的与其最近的一个点acb,构成新的点集acb与一个新的映射

    那么,原映射里的匹配,是源点云到目标点云的有效匹配的条件为,对于源点云里每个点,经过反向查找得到的与其距离小于一个固定的阈值,如下式所示。

    总而言之,本文为了得到有效的点云匹配,进行了正向与反向的查找,并通过反向查找的结果筛选正向查找的匹配。

    在得到有效匹配后便定义目标函数。与通常的点到面的icp函数不同,本文的目标函数也包含双向匹配的过程。传统的点到面的icp的目标函数为:

    而本文的目标函数还包含了一次目标点云到源点云的匹配,其表达式为

    整理一下,可以得到

    B.相关熵度量

    传统的ICP算法的误差度量是用均方根误差,这种方法不能够很好的应对外点(由传感器噪声或者其他原因导致的误匹配),因此后来有许多改进的方法,例如给误差添加核函数等。相关熵也是一个适应外点的鲁棒误差度量。

    根据文献[12],给定点集x,y,并且保证其顺序对应关系,则这两个点集的相关熵可以用公式表达为

    其中,是一个协方差为σ的高斯函数。那么,本文的目标函数可以再次表示为

    再看NDT这里。NDT的核心思想是将源点云先离散成一个个栅格,每个栅格内计算出落在栅格内的点的高斯分布的参数,并使得目标点云经过变换后,使得每个点落在对应的栅格的概率最大。为了使得NDT能够鲁棒应付外点的影响,NDT内每个栅格不是标准的高斯函数,而是以下的形式:

    其中p0是外点的比例(先验),c1,c2是对应的使得概率密度积分为1的参数。这个形式其实没有简单的一阶导与二阶导,因此不利于优化。NDT的做法是,将上述函数的负对数形式用另一个近似函数去拟合,即为:

    本文认为公式17其实是和公式13是有相同的形式的,都是关于误差的二次型,公式17中的d2就是公式13中的σ的作用。不同点在于,根据相关熵的求解理论,σ是可以根据优化来进行调整的,而d2由外点的比例决定,在NDT中是不变的,因此本文认为本文的算法优于NDT。

    C. 基于李代数的流形上的求解器

    根据李群理论,对某个位姿T进行扰动,得到的近似旋转与位移为:

    代入ICP的目标函数,对应有

    带入到公式18中,有

    本文这里给出了CoBigICP的的解析解,相较于传统的基于梯度的求解算法,运算速度要快很多。

    实验

    本文首先将CoBigICP与GICP,NDT与MiNoM方法进行点云的配准结果比较,比较的指标为计算相对位置误差(Relative Pose Error, RPE)。其中CoGICP方法为使用了双向匹配的GICP方法,主要是为了验证相关熵对性能提升的有效性。本文在ETH Hauptgebaude 数据集以及Gazebo Summer数据集上验证了本文提出的算法的有效性。

    接着本文测试了不同的方法对初始位姿扰动的稳定性,如下图所示

    图中的x轴表示平移或者旋转误差,而y轴表示在ETH Hauptgebaude数据集上进行配准得到的误差小于等于对应x轴的误差的概率。从中可以看出,CoBigICP对平移的扰动的稳定性最好,而对旋转的扰动也有较好的效果。

    Abstract

    In this paper, we propose a novel probabilistic variant of iterative closest point (ICP) dubbed as CoBigICP.
    The method leverages both local geometrical information and global noise characteristics. Locally, the 3D structure of both target and source clouds are incorporated into the objective function through bidirectional correspondence. Globally, error metric of correntropy is introduced as noise model to resist outliers. Importantly, the close resemblance between normal-distributions transform (NDT) and correntropy is revealed. To ease the minimization step, an on-manifold parameterization of the special Euclidean group is proposed. Extensive experiments validate that CoBigICP outperforms several well-known and state-of-the-art methods.

    本文仅做学术分享,如有侵权,请联系删文。

    下载1

    在「3D视觉工坊」公众号后台回复:3D视觉即可下载 3D视觉相关资料干货,涉及相机标定、三维重建、立体视觉、SLAM、深度学习、点云后处理、多视图几何等方向。

    下载2

    在「3D视觉工坊」公众号后台回复:3D视觉github资源汇总即可下载包括结构光、标定源码、缺陷检测源码、深度估计与深度补全源码、点云处理相关源码、立体匹配源码、单目、双目3D检测、基于点云的3D检测、6D姿态估计源码汇总等。

    下载3

    在「3D视觉工坊」公众号后台回复:相机标定即可下载独家相机标定学习课件与视频网址;后台回复:立体匹配即可下载独家立体匹配学习课件与视频网址。

    重磅!3DCVer-学术论文写作投稿 交流群已成立

    扫码添加小助手微信,可申请加入3D视觉工坊-学术论文写作与投稿 微信交流群,旨在交流顶会、顶刊、SCI、EI等写作与投稿事宜。

    同时也可申请加入我们的细分方向交流群,目前主要有3D视觉CV&深度学习SLAM三维重建点云后处理自动驾驶、多传感器融合、CV入门、三维测量、VR/AR、3D人脸识别、医疗影像、缺陷检测、行人重识别、目标跟踪、视觉产品落地、视觉竞赛、车牌识别、硬件选型、学术交流、求职交流、ORB-SLAM系列源码交流、深度估计等微信群。

    一定要备注:研究方向+学校/公司+昵称,例如:”3D视觉 + 上海交大 + 静静“。请按照格式备注,可快速被通过且邀请进群。原创投稿也请联系。

    ▲长按加微信群或投稿

    ▲长按关注公众号

    3D视觉从入门到精通知识星球:针对3D视觉领域的视频课程(三维重建系列三维点云系列结构光系列手眼标定相机标定orb-slam3等视频课程)、知识点汇总、入门进阶学习路线、最新paper分享、疑问解答五个方面进行深耕,更有各类大厂的算法工程人员进行技术指导。与此同时,星球将联合知名企业发布3D视觉相关算法开发岗位以及项目对接信息,打造成集技术与就业为一体的铁杆粉丝聚集区,近2000星球成员为创造更好的AI世界共同进步,知识星球入口:

    学习3D视觉核心技术,扫描查看介绍,3天内无条件退款

     圈里有高质量教程资料、答疑解惑、助你高效解决问题

    觉得有用,麻烦给个赞和在看~  

    展开全文
  • 前言二叉树我们都是知道,一个节点有两个子节点,分别为左右子节点,树形结构则分叉左右子树。如何把二叉树转换成双向链表,方式方法有许多,这里主要介绍一种方法,直接在二叉树本身的左右链上做文章,采用递归的...

    前言

    二叉树我们都是知道,一个节点有两个子节点,分别为左右子节点,树形结构则分叉左右子树。如何把二叉树转换成双向链表,方式方法有许多,这里主要介绍一种方法,直接在二叉树本身的左右链上做文章,采用递归的方式。

    方法步骤如下:

    1. 先转换做子树为链式结构,其递归到做子树最左边的叶子节点;

    2. 链表最初的头节点为左子树的最左叶子节点;

    3. 转换右子树的链式结构;

    4. 记录右子树链式的尾节点;

    5. 合并左子树和右子树的链式结构,

    总之,递归深入到左叶子节点,从左子树递归回退向上深入右子树,最后合并链式的一个捣鼓过程;整个过程可以想象为:从最左下角开始,然后上升,接着进入局部右下角,最后合并,按照上述步骤捣鼓捣鼓直到山崩地裂。

    编码

    #include

    struct tree_node_t {

    unsigned int value;

    tree_node_t *left;

    tree_node_t *right;

    };

    int tree_create( tree_node_t *&__root)

    {

    int rc = 0;

    __root = nullptr;

    return rc;

    }

    int tree_push( tree_node_t *&__root, unsigned int __v)

    {

    int rc = 0;

    if ( !__root) {

    __root = new tree_node_t();

    if ( nullptr != __root) {

    __root->value = __v;

    __root->left = nullptr;

    __root->right = nullptr;

    } else { rc = -1; }

    } else {

    if ( __v < __root->value) {

    rc = tree_push( __root->left, __v);

    }

    if ( __v > __root->value) {

    rc = tree_push( __root->right, __v);

    }

    }

    return rc;

    }

    void tree_each( const tree_node_t *__root)

    {

    if ( __root) {

    tree_each( __root->left);

    std::cout << __root->value << " ";

    tree_each( __root->right);

    }

    }

    void tree_to_list( tree_node_t *&__current, tree_node_t *&__head, tree_node_t *&__tail)

    {

    if ( nullptr != __current) {

    tree_node_t *head = nullptr;

    tree_node_t *tail = nullptr;

    /** Link of a left subtree */

    if ( __current->left) {

    (void )tree_to_list( __current->left, head, tail); {

    __head = head;

    __current->left = tail;

    tail->right = __current;

    }

    } else {

    __head = __current;

    }

    /** Link of a right subtree */

    if ( __current->right) {

    (void )tree_to_list( __current->right, head, tail); {

    __tail = tail;

    __current->right = head;

    head->left = __current;

    }

    } else {

    __tail = __current;

    }

    } else {

    __current = nullptr;

    __head = nullptr;

    __tail = nullptr;

    }

    __current = __head;

    }

    void tree_list_each( const tree_node_t *__head)

    {

    if ( __head) {

    std::cout << __head->value << " ";

    tree_list_each( __head->right);

    }

    }

    int main( int argc, const char **argv)

    {

    tree_node_t *root = nullptr;

    tree_create( root);

    srand( time( NULL));

    for ( unsigned int i = 0; i < 32; i++) {

    tree_push( root, rand() % 100);

    }

    std::cout << "\ntree_each:\n";

    tree_each( root);

    tree_node_t *tmp_head = nullptr;

    tree_node_t *tmp_tail = nullptr;

    tree_to_list( root, tmp_head, tmp_tail);

    std::cout << "\ntree_list_each:\n";

    tree_list_each( root);

    std::cout << "\n";

    return 0;

    }

    注:该代码采用c++11实现,毕竟nullptr是c++11引入,编译时加 -std=c++11 选项。

    展开全文
  • 目录: 双向触发二极管 1、双向触发二极管原理与电路示例 2、双向触发二极管分类 ...双向触发二极管亦称二端交流器件(DIAC),属三层结构,具有对称性的二端半导体器件。常用来触发双向可控硅,.
  • 种基于北斗的低功耗双向非实时通信方法【技术领域】[0001]本发明涉及种基于北斗的低功耗双向非实时通信方法,属于北斗系统通信技术领域。【背景技术】[0002]北斗卫星系统具备的短报文通信功能在水文、气象、海洋...
  • 个是我的课程设计做的,请大神指教实验报告实验项目:单相交流调压器Matlab仿真专业班级:电气工程及其自动化1506班姓名:钟*学号:150*实验室号:402 实验组号:16实验时间:批阅时间:指导教师: 成绩:实验目的...
  • 所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。 链表中的每个节点的成员由两部分组成: 1. 数据域:专门用来保存各个成员的信息数据。 2. 指针域:专门用来与其他节点...
  • 哈尔滨理工大学《UNIX程序设计》课程设计报告题 目:单消息队列完成客户/服务器进程之间的双向通信院 系:计算机科学与技术学院 网络工程系班级学号:姓 名:指导教师: 郭锦兰成 绩:2013年12月23日第1章 绪论...
  • 种基于html5网页的服务人员与客户之间针对方案的在线同步交流系统,其特征在于,所述系统包括:服务端,包括第服务模块和第二服务模块;所述第服务模块用于为第客户端和第二客户端提供针对相同或相关目标...
  • 关于面经,小辉之前的文章可以查看《建议找工作的你看一下,无论是校招还是社招》本次分享一个后端朋友最近面试的经验总结,希望能对你有启发。面试概况朋友坐标北京,裸辞在家找工作。线上面试一共58...
  • PAGEPAGE 1PAGE 1单相...实验内容()单相交流调压电路电路(纯电阻负载)1电路的结构与工作原理1.1电路结构单相交流调压电路的电路原理图(电阻性负载)(截图)1.2 工作原理电阻负载单相交流调压电路中,VT1和VT2可以用...
  • 双向晶闸管触发电路工作原理图

    千次阅读 2019-02-21 20:39:08
    调压器电路主要由阻容移相电路和...合上电源开关S,交流电 源电压通过R5、RP向电容器C5充电,当电容器C5两端的电压上升到略高于双向触发二极管ST的转折电压时,ST和双向晶闸管VS相继导通,负载RL得 电工作。 当...
  • 例如,讲中文的人同讲英文的人对话时需要一个翻译,用直流电的笔记本电脑接交流电源时需要一个电源适配器,用计算机访问照相机的 SD 内存卡时需要一个读卡器等。在软件设计中也可能出现:需要开发的具有某种业务功能...
  • Flutter跨平台开发终极之选​zhuanlan.zhihu.com由于最近要做一个安全性比较高的项目,因此需要用到HTTPS进行双向认证。由于设计项目架构的时候,客户端是采用MVVM架构,基于DataBinding + Retrofit +...
  • 单向通信(unidirectional communication)指的是从initiator到target之间的数据流向是单一方向的,或者说initiator和target只能扮演producer和consumer中的一个角色。 在PORT代表了三种端口名:port、export和imp。...
  • 点击下面卡片,关注我呀,每天给你送来AI技术干货!作者|何高乐机构|中国人民大学信息学院硕士研究方向 | 知识表示、知识推理本文主要介绍的是基于双向推理的多跳知识库问答技术。欢迎文章下方评...
  • 要本次毕业设计的题目是应用遗传算法设计出种解决师生双向选择问题的方法,自20世纪为提高毕业设计质量,培养合格的高素质人才,加强毕业设计的指导和管理工作,严格按照名学生只能选择位指导老师,每学生...
  • 本系统主要针对高校研究生管理工作中研究生导师双向选择这培养环节进行设计与开发的,系统的使用对象为系统管理员、导师和研究生三种身份的用户。 1.普通用户(导师和研究生)需求 ①普通用户可以在线获取双向...
  • 使用C语言来实现一个通用的双向链表。利用这个链表来统计一篇文章的不同词数,针对不同单词和同一单词的不同拼写形式进行排序 本文利用了C语言来实现了一个通用的双向链表,其中双向链表的实现借鉴了 实现通用的双向...
  • 为了进一步提高地铁客流预测的准确性,该研究提出了一个由图卷积网络和双向单向长短期记忆网络组成的并行结构深度学习模型(GCN-SBULSTM)。GCN模块将地铁网络视为一个结构化的图,引入K-hop矩阵将出行距离、乘客流和...
  • 这可能是关于 TCP 和 UDP 最好的篇文章!!

    千次阅读 多人点赞 2021-04-26 09:43:57
    文章目录前言运输层概述TCP 和 UDP 前置知识套接字套接字类型套接字处理过程聊聊 IP端口号确定端口号多路复用和多路分解无连接的多路复用和多路分解面向连接的多路复用与多路分解UDPUDP 特点UDP 报文结构TCPTCP 报文...
  • matlab仿真交流调压课设.doc 存档资料成绩:课程设计报告书所属课程名称电气工程基础题目电气工程设计软件计算机操作分院专业班级电气工程及自动化(电牵方向)-2学号学生姓名指导教师2013年6月30日课程设计(论文)评阅...
  • 证书认证分单向认证和双向认证,双向认证是相较于单向认证而言的,单向认证就是只在 APP 侧做证书校验,单向认证有现成的解决方法,比如用各种 bypass ssl 校验的 hook 脚本既可让单向认证失效,例如:JustTrustMe ...
  • 本文实现双向匹配算法,具体算法描述如下: 正向最大算法 设MaxLen表示最大词长,D为分词词典。 (1)从待切分语料中按正向取长度为MaxLen的字串str,令Len=MaxLen; (2)把str与D中的词相匹配; (3)若匹配成功,...
  • 前言大家都知道Vue.js最核心的功能有两是响应式的数据绑定系统,二是组件系统。本文仅探究几乎所有Vue的开篇介绍都会提到的hello world双向绑定是怎样实现的。先讲涉及的知识点,再参考源码,用尽可能少的代码...
  • 可控硅是P1N1P2N2四层三端结构元件,共有三个PN结,分析原理时,可以把它看作由一个PNP管和一个NPN管所组成当阳极A加上正向电压时,BG1和BG2管均处于放大状态。此时,如果从控制极G输入一个正向触发信号,BG2便有...
  • 一种智能交流调压风机转速控制方法【专利...采用智能交流调压与变频器组合使多台不同型号的交流异步电动机共享同一个较大功率变频器。在调速过程中追踪负载转矩实时动态调压,以较小的过载系数实现交流异步电机的有...
  • 双向晶闸管的触发用的光耦驱动mos桥交流输入,无基极引线光耦,DIP-4或SMD-4,常用型号有PC814,TLP620,PS2505-1,LTV-814,K3010交流输入,有基极引线光耦,DIP-6或SMD-6,常用型号有PC733H,TLP630,LTV-733,KP...
  • 电力电子技术是本科高校中电气...本文以交流调压电路(包括单相和三相)为例进行讨论,应用Matlab中的Simulink仿真工具对电力电子电路进行建模仿真,以解决电力电子变流电路的分析的瓶颈所在[2]。1单相交流调压电路1.1...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,559
精华内容 11,423
关键字:

交流是一个双向的过程