精华内容
下载资源
问答
  • * 把二元查找树转变成排序的双向链表 - by Chimomo * * 【思路】按照二叉树的中序遍历正好是按从小到大地顺序遍历全部节点。在遍历的过程中,更改它的逻辑结构。 */ #include <iostream> ...

    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net 

    /*
     * 把二元查找树转变成排序的双向链表 - by Chimomo
     *
     * 【思路】按照二叉树的中序遍历正好是按从小到大地顺序遍历全部节点。在遍历的过程中,更改它的逻辑结构。
     */
    
    #include <iostream>
    
    using namespace std;
    
    /**
     * The binary search tree node.
     */
    struct BSTreeNode {
        int m_nValue; // The value of node.
        BSTreeNode *m_pLeft; // The left child of node.
        BSTreeNode *m_pRight; // The right child of node.
    };
    
    typedef BSTreeNode DoublyLinkedList;
    DoublyLinkedList *pHead = nullptr;
    DoublyLinkedList *pDoublyLinkedList = nullptr;
    
    /**
     * Construct binary search tree recursively.
     * @param pCurrent The current pointer. Use & here since pCurrent will be changed in the function body.
     * @param value The value.
     */
    void ConstructBSTree(BSTreeNode *&pCurrent, int value) {
        if (pCurrent == nullptr) {
            auto pTree = new BSTreeNode();
            pTree->m_pLeft = nullptr;
            pTree->m_pRight = nullptr;
            pTree->m_nValue = value;
            pCurrent = pTree;
        } else {
            if (value > pCurrent->m_nValue) {
                ConstructBSTree(pCurrent->m_pRight, value);
            } else if (value < pCurrent->m_nValue) {
                ConstructBSTree(pCurrent->m_pLeft, value);
            } else {
                cout << "Invalid input, there already have the value!" << endl;
            }
        }
    }
    
    /**
     * Convert binary search tree node to doubly linked list node.
     * @param pCurrent The current pointer.
     */
    void ConvertBSTreeNodeToDoublyLinkedListNode(BSTreeNode *pCurrent) {
        pCurrent->m_pLeft = pDoublyLinkedList;
    
        if (pDoublyLinkedList == nullptr) {
            pHead = pCurrent;
        } else {
            pDoublyLinkedList->m_pRight = pCurrent;
        }
    
        pDoublyLinkedList = pCurrent;
    }
    
    /**
     * Traverse binary search tree (in-order) to convert binary tree to doubly linked list.
     * @param pCurrent The current pointer.
     */
    void TraverseBSTreeInOrder(BSTreeNode *pCurrent) {
        if (pCurrent == nullptr) {
            return;
        } else {
            if (pCurrent->m_pLeft != nullptr) {
                TraverseBSTreeInOrder(pCurrent->m_pLeft);
            }
    
            ConvertBSTreeNodeToDoublyLinkedListNode(pCurrent);
    
            if (pCurrent->m_pRight != nullptr) {
                TraverseBSTreeInOrder(pCurrent->m_pRight);
            }
        }
    }
    
    /**
     * Test program.
     * @param argc The argument count.
     * @param argv The argument array.
     * @return The int.
     */
    int main(int argc, char *argv[]) {
        int value;
        BSTreeNode *pBSTree = nullptr;
        cout << "Please input integers, -1 to end:";
        cin >> value;
    
        while (-1 != value) {
            ConstructBSTree(pBSTree, value);
            cin >> value;
        }
    
        TraverseBSTreeInOrder(pBSTree);
    
        cout << "Print BST:";
        while (pHead) {
            cout << pHead->m_nValue << ' ';
            pHead = pHead->m_pRight;
        }
    
        return 0;
    }
    
    // Output:
    /*
    Please input integers, -1 to end:6 7 8 5 1 3 9 2 4 0 10 -1
    6 7 8 5 1 3 9 2 4 0 10 -1
    Print BST:0 1 2 3 4 5 6 7 8 9 10
    */

     

    展开全文
  • 那么本文将介绍一下另一种特殊的链表结构,叫做 双向链表。 顾名思义,普通的链表都是从 head 开始往后遍历结构内的元素,那么双向链表就是既可以从头开始遍历,又可以从结构的末尾开始遍历。 上一篇文章的跳转链接...

    本系列文章【数据结构与算法】所有完整代码已上传 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前端

    展开全文
  • 双向链表

    万次阅读 2019-12-08 21:39:42
    双向链表 1.创建一个双向链表的结构体,里面有两个指针,可以指向前后两个相邻的节点 /*! *\brief 双向链表节点结构体 */ typedef struct list_node { struct list_node* next; struct list_node* previous; }...

    双向链表

    在这里插入图片描述

    1.创建一个双向链表的结构体,里面有两个指针,可以指向前后两个相邻的节点

    /*!
     *\brief    双向链表节点结构体
     */
    typedef struct list_node
    {
    	struct list_node* next;         
    	struct list_node* previous;
    }list_item_t;
    

    2.双向链表初始化

    /*!
     * \brief    双向链表初始化
     *
     * \param    链表头节点
     *
     * \return   无
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    void list_init(list_item_t* list_head)
    {
    	list_head->next      = list_head;
    	list_head->previous  = list_head;
    }
    

    3.双向链表插入一个节点

    /*!
     * \brief    双向链表在一个节点后面插入一个节点
     *
     * \param    链表节点
     *
     * \return   无
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    void list_insert_after(list_item_t* l, list_item_t* n)
    {
    	l->next->previous = n;
    	n->next = l->next;
    
    	l->next = n;
    	n->previous = l;
    }
    
    
    
    
    /*!
     * \brief    双向链表在一个节点前面插入一个节点
     *
     * \param    链表节点
     *
     * \return   无
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    void list_insert_before(list_item_t* l, list_item_t* n)
    {
    	l->previous->next = n;
    	n->previous = l->previous;
    
    	l->previous = n;
    	n->next = l;
    }
    

    4.删除一个节点

    /*!
     * \brief    双向链表删除一个节点
     *
     * \param    链表节点
     *
     * \return   无
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    void list_remove(list_item_t* l)
    {
    	l->previous->next = l->next;
    	l->next->previous = l->previous;
    
    	l->next = l->previous = l;
    }
    

    5.其他函数

    
    /*!
     * \brief    检查双向链表是否为空
     *
     * \param    链表节点
     *
     * \return   1:空   0:非空
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    uint8_t list_isempty(list_item_t* l)
    {
    	return (uint8_t)(l->next ==  l);
    }
    
    /*!
     * \brief    获取双向链表长度
     *
     * \param    链表节点
     *
     * \return   长度
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    uint32_t list_getlen(list_item_t* l)
    {
    	uint32_t len = 0;
    	const list_item_t* p = l;
    
    	while (p->next != l)
    	{
    		p = p->next;
    		len++;
    	}
    	return len;
    }
    

    双向链表的使用

    双向链表的函数不多,其他应用都是在上面的几个函数的基础上增加的。
    常用的用法有两种,第一种就是改变双向链表结构体,里面增加数据等其他的功能,然后在此基础上操作

    /*!
     *\brief    双向链表节点结构体
     */
    typedef struct list_node
    {
    	struct list_node* next;         
    	struct list_node* previous;
    	uint32_t data;
    }list_item_t;
    

    另一种是直接用上面的双链表函数,重新根据需要构造新的数据结构,比如构造一个学生数据结构体,将双链表当作一个钩子。

    typedef struct student
    {
    	list_item_t  list;
    	uint32_t     grade;
    	char name[20];
    	float score;
    }student_t;
    

    但是这样的话,可以通过学生结构体中的list变量,链接到上下两个学生结构体的list成员,但是我们需要操作的是学生变量,因此我们需要根据结构体的list成员地址,求出学生结构体的地址(这个是linux/rtt系统中常用的操作)。

    /**
     * 根据list的地址 获取结构体的基地址
     */
    #define rt_container_of(ptr, type, member) \
        ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))
    

    创建100个学生数据结构

    uint8_t grade_init(student_t* head, uint32_t num)
    {
    	student_t* pstudent;
    
    	list_init(&head->list); //初始化头节点
    	head->score = (float)num;
    	head->grade = 0;
    	memset(head->name, 0, offsetof(student_t, score) - offsetof(student_t, name));
    
    	while (num--)
    	{
    		pstudent = (student_t*)malloc(sizeof(student_t));
    		
    		if (pstudent == NULL)
    		{
    			return 1; //分配内存失败
    		}
    		list_insert_after(&head->list, &pstudent->list);
    		pstudent->score = 0;
    		pstudent->grade = 0;
    		memset(pstudent->name, 0, offsetof(student_t, score) - offsetof(student_t, name));
    		
    	}
    	return 0;
    }
    
    int main(void)
    {
    	printf("hello world!\n");
    
    	student_t * student_head = (student_t *)malloc(sizeof(student_t));
    
    	uint8_t err = grade_init(student_head, 100);
    	if (err != 0)
    	{
    		printf("初始化失败\n");
    	}
    	
        /*  通过钩子链表访问上下节点 */
    	student_t * student_head3 = rt_container_of(student_head->list.next->next->next, student_t, list);
    
    	student_head3->score = 18.756;
    /* vs 使用strcpy 需要屏蔽警告 */
    #pragma warning(disable : 4996)
    	strcpy(student_head3->name, "张三");
    
    
    	while (1)
    	{
    
    	}
    	return 0;
    }
    
    展开全文
  • 记得在很早之前,我写了一篇关于Android滑动菜单的文章,其中有一个朋友在评论中留言,希望我可以帮他将这个滑动菜单改成双向滑动的方式。当时也没想花太多时间,简单修改了一下就发给了他,结果没想到后来却有一...

    转载请注明出处:http://blog.csdn.net/guolin_blog/article/details/9671609


    记得在很早之前,我写了一篇关于Android滑动菜单的文章,其中有一个朋友在评论中留言,希望我可以帮他将这个滑动菜单改成双向滑动的方式。当时也没想花太多时间,简单修改了一下就发给了他,结果没想到后来却有一大批的朋友都来问我要这份双向滑动菜单的代码。由于这份代码写得很不用心,我发了部分朋友之后实在不忍心继续发下去了,于是决定专门写一篇文章来介绍更好的Android双向滑动菜单的实现方法。


    在开始动手之前先来讲一下实现原理,在一个Activity的布局中需要有三部分,一个是左侧菜单的布局,一个是右侧菜单的布局,一个是内容布局。左侧菜单居屏幕左边缘对齐,右侧菜单居屏幕右边缘对齐,然后内容布局占满整个屏幕,并压在了左侧菜单和右侧菜单的上面。当用户手指向右滑动时,将右侧菜单隐藏,左侧菜单显示,然后通过偏移内容布局的位置,就可以让左侧菜单展现出来。同样的道理,当用户手指向左滑动时,将左侧菜单隐藏,右侧菜单显示,也是通过偏移内容布局的位置,就可以让右侧菜单展现出来。原理示意图所下所示:




    介绍完了原理,我们就开始动手实现吧。新建一个Android项目,项目名就叫做BidirSlidingLayout。然后新建我们最主要的BidirSlidingLayout类,这个类就是实现双向滑动菜单功能的核心类,代码如下所示:

    public class BidirSlidingLayout extends RelativeLayout implements OnTouchListener {
    
    	/**
    	 * 滚动显示和隐藏左侧布局时,手指滑动需要达到的速度。
    	 */
    	public static final int SNAP_VELOCITY = 200;
    
    	/**
    	 * 滑动状态的一种,表示未进行任何滑动。
    	 */
    	public static final int DO_NOTHING = 0;
    
    	/**
    	 * 滑动状态的一种,表示正在滑出左侧菜单。
    	 */
    	public static final int SHOW_LEFT_MENU = 1;
    
    	/**
    	 * 滑动状态的一种,表示正在滑出右侧菜单。
    	 */
    	public static final int SHOW_RIGHT_MENU = 2;
    
    	/**
    	 * 滑动状态的一种,表示正在隐藏左侧菜单。
    	 */
    	public static final int HIDE_LEFT_MENU = 3;
    
    	/**
    	 * 滑动状态的一种,表示正在隐藏右侧菜单。
    	 */
    	public static final int HIDE_RIGHT_MENU = 4;
    
    	/**
    	 * 记录当前的滑动状态
    	 */
    	private int slideState;
    
    	/**
    	 * 屏幕宽度值。
    	 */
    	private int screenWidth;
    
    	/**
    	 * 在被判定为滚动之前用户手指可以移动的最大值。
    	 */
    	private int touchSlop;
    
    	/**
    	 * 记录手指按下时的横坐标。
    	 */
    	private float xDown;
    
    	/**
    	 * 记录手指按下时的纵坐标。
    	 */
    	private float yDown;
    
    	/**
    	 * 记录手指移动时的横坐标。
    	 */
    	private float xMove;
    
    	/**
    	 * 记录手指移动时的纵坐标。
    	 */
    	private float yMove;
    
    	/**
    	 * 记录手机抬起时的横坐标。
    	 */
    	private float xUp;
    
    	/**
    	 * 左侧菜单当前是显示还是隐藏。只有完全显示或隐藏时才会更改此值,滑动过程中此值无效。
    	 */
    	private boolean isLeftMenuVisible;
    
    	/**
    	 * 右侧菜单当前是显示还是隐藏。只有完全显示或隐藏时才会更改此值,滑动过程中此值无效。
    	 */
    	private boolean isRightMenuVisible;
    
    	/**
    	 * 是否正在滑动。
    	 */
    	private boolean isSliding;
    
    	/**
    	 * 左侧菜单布局对象。
    	 */
    	private View leftMenuLayout;
    
    	/**
    	 * 右侧菜单布局对象。
    	 */
    	private View rightMenuLayout;
    
    	/**
    	 * 内容布局对象。
    	 */
    	private View contentLayout;
    
    	/**
    	 * 用于监听滑动事件的View。
    	 */
    	private View mBindView;
    
    	/**
    	 * 左侧菜单布局的参数。
    	 */
    	private MarginLayoutParams leftMenuLayoutParams;
    
    	/**
    	 * 右侧菜单布局的参数。
    	 */
    	private MarginLayoutParams rightMenuLayoutParams;
    
    	/**
    	 * 内容布局的参数。
    	 */
    	private RelativeLayout.LayoutParams contentLayoutParams;
    
    	/**
    	 * 用于计算手指滑动的速度。
    	 */
    	private VelocityTracker mVelocityTracker;
    
    	/**
    	 * 重写BidirSlidingLayout的构造函数,其中获取了屏幕的宽度和touchSlop的值。
    	 * 
    	 * @param context
    	 * @param attrs
    	 */
    	public BidirSlidingLayout(Context context, AttributeSet attrs) {
    		super(context, attrs);
    		WindowManager wm = (WindowManager) context.getSystemService(Context.WINDOW_SERVICE);
    		screenWidth = wm.getDefaultDisplay().getWidth();
    		touchSlop = ViewConfiguration.get(context).getScaledTouchSlop();
    	}
    
    	/**
    	 * 绑定监听滑动事件的View。
    	 * 
    	 * @param bindView
    	 *            需要绑定的View对象。
    	 */
    	public void setScrollEvent(View bindView) {
    		mBindView = bindView;
    		mBindView.setOnTouchListener(this);
    	}
    
    	/**
    	 * 将界面滚动到左侧菜单界面,滚动速度设定为-30.
    	 */
    	public void scrollToLeftMenu() {
    		new LeftMenuScrollTask().execute(-30);
    	}
    
    	/**
    	 * 将界面滚动到右侧菜单界面,滚动速度设定为-30.
    	 */
    	public void scrollToRightMenu() {
    		new RightMenuScrollTask().execute(-30);
    	}
    
    	/**
    	 * 将界面从左侧菜单滚动到内容界面,滚动速度设定为30.
    	 */
    	public void scrollToContentFromLeftMenu() {
    		new LeftMenuScrollTask().execute(30);
    	}
    
    	/**
    	 * 将界面从右侧菜单滚动到内容界面,滚动速度设定为30.
    	 */
    	public void scrollToContentFromRightMenu() {
    		new RightMenuScrollTask().execute(30);
    	}
    
    	/**
    	 * 左侧菜单是否完全显示出来,滑动过程中此值无效。
    	 * 
    	 * @return 左侧菜单完全显示返回true,否则返回false。
    	 */
    	public boolean isLeftLayoutVisible() {
    		return isLeftMenuVisible;
    	}
    
    	/**
    	 * 右侧菜单是否完全显示出来,滑动过程中此值无效。
    	 * 
    	 * @return 右侧菜单完全显示返回true,否则返回false。
    	 */
    	public boolean isRightLayoutVisible() {
    		return isRightMenuVisible;
    	}
    
    	/**
    	 * 在onLayout中重新设定左侧菜单、右侧菜单、以及内容布局的参数。
    	 */
    	@Override
    	protected void onLayout(boolean changed, int l, int t, int r, int b) {
    		super.onLayout(changed, l, t, r, b);
    		if (changed) {
    			// 获取左侧菜单布局对象
    			leftMenuLayout = getChildAt(0);
    			leftMenuLayoutParams = (MarginLayoutParams) leftMenuLayout.getLayoutParams();
    			// 获取右侧菜单布局对象
    			rightMenuLayout = getChildAt(1);
    			rightMenuLayoutParams = (MarginLayoutParams) rightMenuLayout.getLayoutParams();
    			// 获取内容布局对象
    			contentLayout = getChildAt(2);
    			contentLayoutParams = (RelativeLayout.LayoutParams) contentLayout.getLayoutParams();
    			contentLayoutParams.width = screenWidth;
    			contentLayout.setLayoutParams(contentLayoutParams);
    		}
    	}
    
    	@Override
    	public boolean onTouch(View v, MotionEvent event) {
    		createVelocityTracker(event);
    		switch (event.getAction()) {
    		case MotionEvent.ACTION_DOWN:
    			// 手指按下时,记录按下时的坐标
    			xDown = event.getRawX();
    			yDown = event.getRawY();
    			// 将滑动状态初始化为DO_NOTHING
    			slideState = DO_NOTHING;
    			break;
    		case MotionEvent.ACTION_MOVE:
    			xMove = event.getRawX();
    			yMove = event.getRawY();
    			// 手指移动时,对比按下时的坐标,计算出移动的距离。
    			int moveDistanceX = (int) (xMove - xDown);
    			int moveDistanceY = (int) (yMove - yDown);
    			// 检查当前的滑动状态
    			checkSlideState(moveDistanceX, moveDistanceY);
    			// 根据当前滑动状态决定如何偏移内容布局
    			switch (slideState) {
    			case SHOW_LEFT_MENU:
    				contentLayoutParams.rightMargin = -moveDistanceX;
    				checkLeftMenuBorder();
    				contentLayout.setLayoutParams(contentLayoutParams);
    				break;
    			case HIDE_LEFT_MENU:
    				contentLayoutParams.rightMargin = -leftMenuLayoutParams.width - moveDistanceX;
    				checkLeftMenuBorder();
    				contentLayout.setLayoutParams(contentLayoutParams);
    			case SHOW_RIGHT_MENU:
    				contentLayoutParams.leftMargin = moveDistanceX;
    				checkRightMenuBorder();
    				contentLayout.setLayoutParams(contentLayoutParams);
    				break;
    			case HIDE_RIGHT_MENU:
    				contentLayoutParams.leftMargin = -rightMenuLayoutParams.width + moveDistanceX;
    				checkRightMenuBorder();
    				contentLayout.setLayoutParams(contentLayoutParams);
    			default:
    				break;
    			}
    			break;
    		case MotionEvent.ACTION_UP:
    			xUp = event.getRawX();
    			int upDistanceX = (int) (xUp - xDown);
    			if (isSliding) {
    				// 手指抬起时,进行判断当前手势的意图
    				switch (slideState) {
    				case SHOW_LEFT_MENU:
    					if (shouldScrollToLeftMenu()) {
    						scrollToLeftMenu();
    					} else {
    						scrollToContentFromLeftMenu();
    					}
    					break;
    				case HIDE_LEFT_MENU:
    					if (shouldScrollToContentFromLeftMenu()) {
    						scrollToContentFromLeftMenu();
    					} else {
    						scrollToLeftMenu();
    					}
    					break;
    				case SHOW_RIGHT_MENU:
    					if (shouldScrollToRightMenu()) {
    						scrollToRightMenu();
    					} else {
    						scrollToContentFromRightMenu();
    					}
    					break;
    				case HIDE_RIGHT_MENU:
    					if (shouldScrollToContentFromRightMenu()) {
    						scrollToContentFromRightMenu();
    					} else {
    						scrollToRightMenu();
    					}
    					break;
    				default:
    					break;
    				}
    			} else if (upDistanceX < touchSlop && isLeftMenuVisible) {
    				// 当左侧菜单显示时,如果用户点击一下内容部分,则直接滚动到内容界面
    				scrollToContentFromLeftMenu();
    			} else if (upDistanceX < touchSlop && isRightMenuVisible) {
    				// 当右侧菜单显示时,如果用户点击一下内容部分,则直接滚动到内容界面
    				scrollToContentFromRightMenu();
    			}
    			recycleVelocityTracker();
    			break;
    		}
    		if (v.isEnabled()) {
    			if (isSliding) {
    				// 正在滑动时让控件得不到焦点
    				unFocusBindView();
    				return true;
    			}
    			if (isLeftMenuVisible || isRightMenuVisible) {
    				// 当左侧或右侧布局显示时,将绑定控件的事件屏蔽掉
    				return true;
    			}
    			return false;
    		}
    		return true;
    	}
    
    	/**
    	 * 根据手指移动的距离,判断当前用户的滑动意图,然后给slideState赋值成相应的滑动状态值。
    	 * 
    	 * @param moveDistanceX
    	 *            横向移动的距离
    	 * @param moveDistanceY
    	 *            纵向移动的距离
    	 */
    	private void checkSlideState(int moveDistanceX, int moveDistanceY) {
    		if (isLeftMenuVisible) {
    			if (!isSliding && Math.abs(moveDistanceX) >= touchSlop && moveDistanceX < 0) {
    				isSliding = true;
    				slideState = HIDE_LEFT_MENU;
    			}
    		} else if (isRightMenuVisible) {
    			if (!isSliding && Math.abs(moveDistanceX) >= touchSlop && moveDistanceX > 0) {
    				isSliding = true;
    				slideState = HIDE_RIGHT_MENU;
    			}
    		} else {
    			if (!isSliding && Math.abs(moveDistanceX) >= touchSlop && moveDistanceX > 0
    					&& Math.abs(moveDistanceY) < touchSlop) {
    				isSliding = true;
    				slideState = SHOW_LEFT_MENU;
    				contentLayoutParams.addRule(RelativeLayout.ALIGN_PARENT_LEFT, 0);
    				contentLayoutParams.addRule(RelativeLayout.ALIGN_PARENT_RIGHT);
    				contentLayout.setLayoutParams(contentLayoutParams);
    				// 如果用户想要滑动左侧菜单,将左侧菜单显示,右侧菜单隐藏
    				leftMenuLayout.setVisibility(View.VISIBLE);
    				rightMenuLayout.setVisibility(View.GONE);
    			} else if (!isSliding && Math.abs(moveDistanceX) >= touchSlop && moveDistanceX < 0
    					&& Math.abs(moveDistanceY) < touchSlop) {
    				isSliding = true;
    				slideState = SHOW_RIGHT_MENU;
    				contentLayoutParams.addRule(RelativeLayout.ALIGN_PARENT_RIGHT, 0);
    				contentLayoutParams.addRule(RelativeLayout.ALIGN_PARENT_LEFT);
    				contentLayout.setLayoutParams(contentLayoutParams);
    				// 如果用户想要滑动右侧菜单,将右侧菜单显示,左侧菜单隐藏
    				rightMenuLayout.setVisibility(View.VISIBLE);
    				leftMenuLayout.setVisibility(View.GONE);
    			}
    		}
    	}
    
    	/**
    	 * 在滑动过程中检查左侧菜单的边界值,防止绑定布局滑出屏幕。
    	 */
    	private void checkLeftMenuBorder() {
    		if (contentLayoutParams.rightMargin > 0) {
    			contentLayoutParams.rightMargin = 0;
    		} else if (contentLayoutParams.rightMargin < -leftMenuLayoutParams.width) {
    			contentLayoutParams.rightMargin = -leftMenuLayoutParams.width;
    		}
    	}
    
    	/**
    	 * 在滑动过程中检查右侧菜单的边界值,防止绑定布局滑出屏幕。
    	 */
    	private void checkRightMenuBorder() {
    		if (contentLayoutParams.leftMargin > 0) {
    			contentLayoutParams.leftMargin = 0;
    		} else if (contentLayoutParams.leftMargin < -rightMenuLayoutParams.width) {
    			contentLayoutParams.leftMargin = -rightMenuLayoutParams.width;
    		}
    	}
    
    	/**
    	 * 判断是否应该滚动将左侧菜单展示出来。如果手指移动距离大于左侧菜单宽度的1/2,或者手指移动速度大于SNAP_VELOCITY,
    	 * 就认为应该滚动将左侧菜单展示出来。
    	 * 
    	 * @return 如果应该将左侧菜单展示出来返回true,否则返回false。
    	 */
    	private boolean shouldScrollToLeftMenu() {
    		return xUp - xDown > leftMenuLayoutParams.width / 2 || getScrollVelocity() > SNAP_VELOCITY;
    	}
    
    	/**
    	 * 判断是否应该滚动将右侧菜单展示出来。如果手指移动距离大于右侧菜单宽度的1/2,或者手指移动速度大于SNAP_VELOCITY,
    	 * 就认为应该滚动将右侧菜单展示出来。
    	 * 
    	 * @return 如果应该将右侧菜单展示出来返回true,否则返回false。
    	 */
    	private boolean shouldScrollToRightMenu() {
    		return xDown - xUp > rightMenuLayoutParams.width / 2 || getScrollVelocity() > SNAP_VELOCITY;
    	}
    
    	/**
    	 * 判断是否应该从左侧菜单滚动到内容布局,如果手指移动距离大于左侧菜单宽度的1/2,或者手指移动速度大于SNAP_VELOCITY,
    	 * 就认为应该从左侧菜单滚动到内容布局。
    	 * 
    	 * @return 如果应该从左侧菜单滚动到内容布局返回true,否则返回false。
    	 */
    	private boolean shouldScrollToContentFromLeftMenu() {
    		return xDown - xUp > leftMenuLayoutParams.width / 2 || getScrollVelocity() > SNAP_VELOCITY;
    	}
    
    	/**
    	 * 判断是否应该从右侧菜单滚动到内容布局,如果手指移动距离大于右侧菜单宽度的1/2,或者手指移动速度大于SNAP_VELOCITY,
    	 * 就认为应该从右侧菜单滚动到内容布局。
    	 * 
    	 * @return 如果应该从右侧菜单滚动到内容布局返回true,否则返回false。
    	 */
    	private boolean shouldScrollToContentFromRightMenu() {
    		return xUp - xDown > rightMenuLayoutParams.width / 2 || getScrollVelocity() > SNAP_VELOCITY;
    	}
    
    	/**
    	 * 创建VelocityTracker对象,并将触摸事件加入到VelocityTracker当中。
    	 * 
    	 * @param event
    	 *            右侧布局监听控件的滑动事件
    	 */
    	private void createVelocityTracker(MotionEvent event) {
    		if (mVelocityTracker == null) {
    			mVelocityTracker = VelocityTracker.obtain();
    		}
    		mVelocityTracker.addMovement(event);
    	}
    
    	/**
    	 * 获取手指在绑定布局上的滑动速度。
    	 * 
    	 * @return 滑动速度,以每秒钟移动了多少像素值为单位。
    	 */
    	private int getScrollVelocity() {
    		mVelocityTracker.computeCurrentVelocity(1000);
    		int velocity = (int) mVelocityTracker.getXVelocity();
    		return Math.abs(velocity);
    	}
    
    	/**
    	 * 回收VelocityTracker对象。
    	 */
    	private void recycleVelocityTracker() {
    		mVelocityTracker.recycle();
    		mVelocityTracker = null;
    	}
    
    	/**
    	 * 使用可以获得焦点的控件在滑动的时候失去焦点。
    	 */
    	private void unFocusBindView() {
    		if (mBindView != null) {
    			mBindView.setPressed(false);
    			mBindView.setFocusable(false);
    			mBindView.setFocusableInTouchMode(false);
    		}
    	}
    
    	class LeftMenuScrollTask extends AsyncTask<Integer, Integer, Integer> {
    
    		@Override
    		protected Integer doInBackground(Integer... speed) {
    			int rightMargin = contentLayoutParams.rightMargin;
    			// 根据传入的速度来滚动界面,当滚动到达边界值时,跳出循环。
    			while (true) {
    				rightMargin = rightMargin + speed[0];
    				if (rightMargin < -leftMenuLayoutParams.width) {
    					rightMargin = -leftMenuLayoutParams.width;
    					break;
    				}
    				if (rightMargin > 0) {
    					rightMargin = 0;
    					break;
    				}
    				publishProgress(rightMargin);
    				// 为了要有滚动效果产生,每次循环使线程睡眠一段时间,这样肉眼才能够看到滚动动画。
    				sleep(15);
    			}
    			if (speed[0] > 0) {
    				isLeftMenuVisible = false;
    			} else {
    				isLeftMenuVisible = true;
    			}
    			isSliding = false;
    			return rightMargin;
    		}
    
    		@Override
    		protected void onProgressUpdate(Integer... rightMargin) {
    			contentLayoutParams.rightMargin = rightMargin[0];
    			contentLayout.setLayoutParams(contentLayoutParams);
    			unFocusBindView();
    		}
    
    		@Override
    		protected void onPostExecute(Integer rightMargin) {
    			contentLayoutParams.rightMargin = rightMargin;
    			contentLayout.setLayoutParams(contentLayoutParams);
    		}
    	}
    
    	class RightMenuScrollTask extends AsyncTask<Integer, Integer, Integer> {
    
    		@Override
    		protected Integer doInBackground(Integer... speed) {
    			int leftMargin = contentLayoutParams.leftMargin;
    			// 根据传入的速度来滚动界面,当滚动到达边界值时,跳出循环。
    			while (true) {
    				leftMargin = leftMargin + speed[0];
    				if (leftMargin < -rightMenuLayoutParams.width) {
    					leftMargin = -rightMenuLayoutParams.width;
    					break;
    				}
    				if (leftMargin > 0) {
    					leftMargin = 0;
    					break;
    				}
    				publishProgress(leftMargin);
    				// 为了要有滚动效果产生,每次循环使线程睡眠一段时间,这样肉眼才能够看到滚动动画。
    				sleep(15);
    			}
    			if (speed[0] > 0) {
    				isRightMenuVisible = false;
    			} else {
    				isRightMenuVisible = true;
    			}
    			isSliding = false;
    			return leftMargin;
    		}
    
    		@Override
    		protected void onProgressUpdate(Integer... leftMargin) {
    			contentLayoutParams.leftMargin = leftMargin[0];
    			contentLayout.setLayoutParams(contentLayoutParams);
    			unFocusBindView();
    		}
    
    		@Override
    		protected void onPostExecute(Integer leftMargin) {
    			contentLayoutParams.leftMargin = leftMargin;
    			contentLayout.setLayoutParams(contentLayoutParams);
    		}
    	}
    
    	/**
    	 * 使当前线程睡眠指定的毫秒数。
    	 * 
    	 * @param millis
    	 *            指定当前线程睡眠多久,以毫秒为单位
    	 */
    	private void sleep(long millis) {
    		try {
    			Thread.sleep(millis);
    		} catch (InterruptedException e) {
    			e.printStackTrace();
    		}
    	}
    }

    以上代码注释已经写得非常详细,我再来简单解释一下。首先在onLayout()方法中分别获取到左侧菜单、右侧菜单和内容布局的参数,并将内容布局的宽度重定义成屏幕的宽度,这样就可以保证内容布局既能覆盖住下面的菜单布局,还能偏移出屏幕。然后在onTouch()方法中监听触屏事件,以判断用户手势的意图。这里事先定义好了几种滑动状态,DO_NOTHING表示没有进行任何滑动,SHOW_LEFT_MENU表示用户想要滑出左侧菜单,SHOW_RIGHT_MENU表示用户想要滑出右侧菜单,HIDE_LEFT_MENU表示用户想要隐藏左侧菜单,HIDE_RIGHT_MENU表示用户想要隐藏右侧菜单,在checkSlideState()方法中判断出用户到底是想进行哪一种滑动操作,并给slideState变量赋值,然后根据slideState的值决定如何偏移内容布局。接着当用户手指离开屏幕时,会根据当前的滑动距离,决定后续的滚动方向,通过LeftMenuScrollTask和RightMenuScrollTask来完成完整的滑动过程。另外在滑动的过程,内容布局上的事件会被屏蔽掉,主要是通过一系列的return操作实现的,对这一部分不理解的朋友,请参阅 Android事件分发机制完全解析,带你从源码的角度彻底理解 。


    然后我们看一下setScrollEvent方法,这个方法接收一个View作为参数,然后为这个View绑定了一个touch事件。这是什么意思呢?让我们来想象一个场景,如果内容布局是一个LinearLayout,我可以通过监听LinearLayout上的touch事件来控制它的偏移。但是如果内容布局的LinearLayout里面加入了一个ListView,而这个ListView又充满了整个LinearLayout,这个时候LinearLayout将不可能再被touch到了,这个时候我们就需要将touch事件注册到ListView上。setScrollEvent方法也就是提供了一个注册接口,touch事件将会注册到传入的View上。


    接下来打开或新建activity_main.xml文件,加入如下代码:

    <com.example.bidirslidinglayout.BidirSlidingLayout xmlns:android="http://schemas.android.com/apk/res/android"
        xmlns:tools="http://schemas.android.com/tools"
        android:id="@+id/bidir_sliding_layout"
        android:layout_width="fill_parent"
        android:layout_height="fill_parent" >
    
        <RelativeLayout
            android:id="@+id/left_menu"
            android:layout_width="270dip"
            android:layout_height="fill_parent"
            android:layout_alignParentLeft="true"
            android:background="#00ccff"
            android:visibility="invisible" >
    
            <TextView
                android:layout_width="wrap_content"
                android:layout_height="wrap_content"
                android:layout_centerInParent="true"
                android:text="This is left menu"
                android:textColor="#000000"
                android:textSize="28sp" />
        </RelativeLayout>
    
        <RelativeLayout
            android:id="@+id/right_menu"
            android:layout_width="270dip"
            android:layout_height="fill_parent"
            android:layout_alignParentRight="true"
            android:background="#00ffcc"
            android:visibility="invisible" >
    
            <TextView
                android:layout_width="wrap_content"
                android:layout_height="wrap_content"
                android:layout_centerInParent="true"
                android:text="This is right menu"
                android:textColor="#000000"
                android:textSize="28sp" />
        </RelativeLayout>
    
        <LinearLayout
            android:id="@+id/content"
            android:layout_width="320dip"
            android:layout_height="fill_parent"
            android:background="#e9e9e9" >
    
            <ListView
                android:id="@+id/contentList"
                android:layout_width="fill_parent"
                android:layout_height="fill_parent"
                android:scrollbars="none"
                android:cacheColorHint="#00000000" >
            </ListView>
        </LinearLayout>
    
    </com.example.bidirslidinglayout.BidirSlidingLayout>

    可以看到,我们使用了自定义的BidirSlidingLayout作为根布局,然后依次加入了三个子布局分别作为左侧菜单、右侧菜单和内容的布局。左侧菜单和右侧菜单中都只是简单地放入了一个TextView用于显示一段文字,内容布局中放入了一个ListView。注意要让左侧菜单和父布局左边缘对齐,右侧菜单和父布局右边缘对齐。


    最后打开或者创建MainActivity作为程序的主Activity,代码如下所示:

    public class MainActivity extends Activity {
    
    	/**
    	 * 双向滑动菜单布局
    	 */
    	private BidirSlidingLayout bidirSldingLayout;
    
    	/**
    	 * 在内容布局上显示的ListView
    	 */
    	private ListView contentList;
    
    	/**
    	 * ListView的适配器
    	 */
    	private ArrayAdapter<String> contentListAdapter;
    
    	/**
    	 * 用于填充contentListAdapter的数据源。
    	 */
    	private String[] contentItems = { "Content Item 1", "Content Item 2", "Content Item 3",
    			"Content Item 4", "Content Item 5", "Content Item 6", "Content Item 7",
    			"Content Item 8", "Content Item 9", "Content Item 10", "Content Item 11",
    			"Content Item 12", "Content Item 13", "Content Item 14", "Content Item 15",
    			"Content Item 16" };
    
    	@Override
    	protected void onCreate(Bundle savedInstanceState) {
    		super.onCreate(savedInstanceState);
    		setContentView(R.layout.activity_main);
    		bidirSldingLayout = (BidirSlidingLayout) findViewById(R.id.bidir_sliding_layout);
    		contentList = (ListView) findViewById(R.id.contentList);
    		contentListAdapter = new ArrayAdapter<String>(this, android.R.layout.simple_list_item_1,
    				contentItems);
    		contentList.setAdapter(contentListAdapter);
    		bidirSldingLayout.setScrollEvent(contentList);
    	}
    
    }

    这里我们给ListView填充了几条数据,又通过findViewById()方法获取到了BidirSlidingLayout对象,然后调用它的setScrollEvent()方法,将ListView进行绑定,这样就可以通过左右滑动ListView来展示左侧菜单和右侧菜单了。


    好了,全部编码工作都已完成,现在让我们运行一下程序吧,效果如下图所示:




    看起来还是挺不错的吧!并且更重要的是,以后我们在项目的任何地方都可以轻松加入双向滑动菜单功能,只需要以下两步即可:


    1. 在Acitivty的layout中引入我们自定义的BidirSlidingLayout布局,并且给这个布局要加入三个直接子元素。

    2. 在Activity中通过setScrollEvent方法,给一个View注册touch事件。


    如此一来,一分钟实现双向滑动菜单功能妥妥的。

    好了,今天的讲解到此结束,有疑问的朋友请在下面留言。


    源码下载,请点击这里

    带按钮的版本下载,请点击这里


    关注我的技术公众号,每天都有优质技术文章推送。关注我的娱乐公众号,工作、学习累了的时候放松一下自己。

    微信扫一扫下方二维码即可关注:

            

    展开全文
  • 双向链表的双向遍历

    千次阅读 2020-03-04 22:01:58
    双向链表的双向遍历 双向链表相比较于单向链表的优势之一就是可以快速遍历,对于单向链表只能借助于单个指针逐个遍历,而对于双向链表而言因为每个节点都存在一个前指针和后指针,所以可以借助于两个指针双向遍历,...
  • 双向 LSTM

    万次阅读 2017-08-11 11:35:45
    为什么用双向 LSTM 什么是双向 LSTM 例子 为什么用双向 LSTM?单向的 RNN,是根据前面的信息推出后面的,但有时候只看前面的词是不够的, 例如,我今天不舒服,我打算__一天。只根据‘不舒服‘,可能推出我打算‘去...
  • 创建双向链表(详解)

    万次阅读 多人点赞 2018-11-25 16:18:46
    双向链表操作 在学习了单链表之后,就顺带学习了双链表的操作。 什么是双链表? 双链表顾名思义,就是链表由单向的链变成了双向链。 使用这种数据结构,我们可以不再拘束于单链表的单向创建于遍历等操作,大大减少...
  • uKey双向认证https

    万次阅读 2020-10-19 17:39:00
    双向认证:不仅仅需要用户浏览器校验服务器数字证书,还需要服务器端验证用户是否是可信的; 二 单向认证流程(springboot项目为例) 1 制作证书 直接利用keytools工具生成 keytool -genkey -alias client -...
  • 双向LSTM

    万次阅读 2018-05-15 20:31:55
    双向LSTM是传统LSTM的扩展,可以提高序列分类问题的模型性能。在输入序列的所有时间步长可用的问题中,双向LSTM在输入序列上训练两个而不是一个LSTM。输入序列中的第一个是原样的,第二个是输入序列的反转副本。这...
  • 双向bfs

    千次阅读 2018-10-23 20:20:28
    自从暑假学长讲过这个之后,现在才开始写第一道双向bfs题目。其实双向bfs很简单就是分别从起点和终点做两个bfs,以此大幅度减少搜索的状态数,从而解决一些普通单向bfs容易超时的问题。 q1从起点bfs的队列,q2从...
  • 双向端口

    2018-10-17 15:00:50
    三态缓冲器也称三态门,其典型应用是双向端口,常用于双向数据总线的构建。在数字电路中,逻辑输出有两个正常态:低电平状态(逻辑0)和高电平状态(逻辑1),此外,电路还有不属于0和1的高阻态(逻辑Z)。所谓高阻...
  • 华为 路由双点双向引入

    千次阅读 多人点赞 2021-01-07 10:30:24
    双点双向重发布(OSPF、IS-IS) 路由环路的出现就是同时存在次优路径和路由回馈;如果想解决路由环路的问题,那么解决次优路径或路由回馈的其中一个问题,就能解决路由环路的问题了。
  • 双向口与双向口的差别

    千次阅读 2019-03-31 10:15:41
    双向口与双向口的差别 P0口作为地址总线(低8位)及数据总线使用时,为双向口。作为通用的I/O口使用时,需加上拉电阻,这时为准双向口。而P1口、P2口、P3口均为准双向口。 双向口P0与P1口、P2口、P3口这3个准...
  • 双向链表1.1 双向链表创建1.2 双向链表插入结点1.3 双向链表删除指定结点1.4 双向链表删除指定元素1.5 双向链表查找元素位置1.6 双向链表更新结点数据1.7 双向链表遍历2. 双向循环链表2.1 双向循环链表创建2.2 双向...
  • 双向队列

    2015-05-08 21:17:31
    C++ Double Ended Queues(双向队列) 双向队列和向量很相似,但是它允许在容器头部快速插入和删除(就像在尾部一样)。 Constructors 创建一个新双向队列 Operators 比较和赋值双向队列...
  • 看动画学算法之:双向队列dequeue

    万次阅读 2020-07-30 15:04:15
    文章目录简介双向队列的实现双向队列的数组实现双向队列的动态数组实现双向队列的链表实现双向链表的时间复杂度 简介 dequeue指的是双向队列,可以分别从队列的头部插入和获取数据,也可以从队列的尾部插入和获取...
  • 双向链表、双端(双向)链表、循环(双向)链表示意(简)图: 声明:下面各图中,箭头指向的是整个节点,而不是指向节点中的prior或next。 双向链表:只有一个指针指向最开始的结点。 双端(双向)链表:有两个指针...
  • 自适应双向运动估计

    千次阅读 2020-11-29 00:13:41
    这里,算法创新点主要在于将单向运动估计和双向运动估计进行有效的结合,从而结合了两种算法的优点,提高了运动算法的性能。 首先通过单向运动估计的方法快速得到运动向量作为双向运动估计的初始值,然后进行块...
  • 双向循环链表

    千次阅读 2020-06-11 16:58:34
    复习到数据结构的双向循环链表,用程序记录一下 main.cpp #include <iostream> #include "linklist.h" using namespace std; int main(int argc, char *argv[]) { node *head = NULL; list_init(&head...
  • 单片机双向口与准双向

    千次阅读 2016-02-28 17:23:42
    真正的双向口正如其名,就是真正的双向io不需要任何预操作可直接读入读出。 双向IO口与准双向IO口的区别 http://surge2006.blog.163.com/blog/static/13176613120100610206943/ 双向IO口与准双
  • 51单片机双向口和准双向口有什么区别

    万次阅读 多人点赞 2018-07-28 09:52:57
    双向口与准双向口的区别主要是:准双向口I/O口操作时做数据输入时需要对其置1,否则若前一位为低电平,后一位输入的电平为高则MOS管拉不起来导致出错。而双向口则不需要做此动作,因为双向口有悬浮态。 准双向口就是...
  • 双向链表实现栈和队列

    万次阅读 2021-02-05 14:31:34
    双向链表实现栈和队列前言1. 双向链表2. 栈 --》 双向链表 首部加 首部出 O(1)3. 队列 --》 双向链表 首部加 尾部出 O(1) 前言 栈 --》 双向链表 首部加 首部出 O(1) 队列 --》 双向链表 首部加 尾部出 O(1) 1. ...
  • 当时拿到这个问题,第一时间去网上百度https双向认证的案例,试了好多种,有单项认证的实现,还有双向认证基于浏览器端的访问,对于两个系统之间的https双向认证很少,自己也浪费了好多时间没有成功,于是,下定决心...
  • 策略路由 路由策略 双点双向引入

    千次阅读 多人点赞 2020-07-10 01:33:17
    策略路由 路由策略 双点双向引入 一、策略路由 (一)策略路由–Policy-Based Routing—PBR 1、什么是策略路由: 对特定数据报文不按照路由表内的条目执行转发,根据需要按照某种策略改变数据报文转发路径。 2、...
  • 双向链表的删除操作

    万次阅读 2021-03-19 19:32:50
    //从双向链表中删除一个节点 //说明 //1.对于双向链表,我们可以直接找到删除的这个节点 //2.找到后,自我删除即可 public void del(int no) { //判断当前链表是否为空 if (head.next==null){//空链表 System...
  • JAVA双向链表

    千次阅读 2019-04-19 16:29:58
    java双向链表操作 双向链表的每一个结点都有一条指向其后继结点的next指针和一条指向其前结点的pre指针。 双向链表的插入图示: 双向链表的删除图示: import java.io.IOException; import java.util.Scanner; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 119,312
精华内容 47,724
关键字:

双向