精华内容
下载资源
问答
  • 结构 非常得类似我们之前讲到过的树结构,但前者没有很多的从属关系,更多的是各个数据之间的相关联系。在数学的概念中,后者是前者的一种,不过在数据结构中我们还是认为两者有所区别,尽管如此,我们在学习图...

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

    图结构 非常得类似我们之前讲到过的树结构,但前者没有很多的从属关系,更多的是各个数据之间的相关联系。在数学的概念中,后者是前者的一种,不过在数据结构中我们还是认为两者有所区别,尽管如此,我们在学习图结构的时候仍可以稍微借鉴一下树结构的思想

    这里放上之前树结构的文章地址,没看过的小伙伴可以查阅一下:

    【数据结构与算法】详解什么是树结构,并用代码手动实现一个二叉查找树

    接下来让我们来一起学习一下图结构吧

    在这里插入图片描述

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

    一、什么是图结构

    是由顶点的集合和边的集合组成的。

    在我们的身边有很多用到图结构的地方,例如地铁线路图

    在这里插入图片描述
    地铁线路图中每一个站点都可以看成一个顶点,而连接着每个站点的线路可以看作是

    其中是可以有方向的。例如从 站点1站点2 是可以的,但是反过来 站点2站点1 是不可以的,那么此时就说 顶点1顶点2 之间的边是有方向的,方向为 顶点1 -> 顶点2

    二、图结构的术语

    文章开头说过,图结构与树结构有很多的相似之处,因此我们还是要先来介绍一些下文会提到的图结构中的术语

    术语 含义
    顶点 图中的某个结点
    顶点之间连线
    相邻顶点 由同一条边连接在一起的顶点
    一个顶点的相邻顶点个数
    简单路径 由一个顶点到另一个顶点的路线,且没有重复经过顶点
    回路 第一个顶点和最后一个顶点的相同的路径
    无向图 图中所有的边都没有方向
    有向图 图中所有的边都有方向
    无权图 图中的边没有权重值
    有权图 图中的边带有一定的权重值

    我们再来看个图的例子,借此来更详细地介绍一下每个术语地含义,如图

    在这里插入图片描述
    该图为某某县地村落分布图,我们可以把其看成是一个图结构,其中每个村看成是一个顶点,每两个村之间可能通了一条路方便来往,例如 A村和D村之间就有一条路线1,我们称之为

    邻村表示只需要经过一条边就可以到达另一个村,那么我们就说这两个村互为邻村,也可以称它们互为相邻顶点。每个村都会有一个甚至多个邻村,例如D村的邻村有 A村 、C村 、F村,此时我们就说顶点D(D村)的为3

    假设有一天,你要从A村前往E村,你选择的路线是这样的,如图所示
    在这里插入图片描述
    途中我们经过了 顶点A顶点C顶点E ,没有重复经过某个顶点,因此我们称这条路线为简单路径

    此时,若你选择的路线是这样的,如图所示

    在这里插入图片描述
    途中经过两次 顶点C ,此时我们就不能称这条路线为简单路径了

    到了晚上,你准备起身回家,但选择经过B村再回家,那么此时你一整天的路线是这样的,如图所示
    在这里插入图片描述
    因为你当前的出发点和结束点都是A村(顶点A),因此这样的路线我们称之为回路

    第二天,你接到一个任务,尽快将一个包裹送往E村,为了节省时间,你查阅资料获取到了各条路的长度,如图所示

    在这里插入图片描述
    此时的图结构上每条边就带上了权重值,我们称这个图为有权图

    通过计算,最后选择了 A村 -> C村 -> E村 这条路线,等到包裹送到E村以后,你正准备原路返回,但发现来时的路都是单向的,现在不允许走这条路回去了,于是你又查阅资料,查看这个县各条路的方向情况,结果如图所示

    在这里插入图片描述
    此时的图结构上每条边都有一定的方向,我们称这个图为有向图

    最后你选择了 E村 -> B村 -> A村 这条路线成功回到了家

    三、图的表示

    上面我们在介绍图的时候,都是用一个形象的图片来讲解的,但在程序中,这样的表达方式显然不是我们想要的,因此我们要找到别的方式来表示结构

    图结构的常见的两个表达方式: 邻接矩阵邻接表

    (1)邻接矩阵

    顾名思义,邻接矩阵就像数学中的矩阵,我们只不过是借此来表示图结构,如图所示,现在有一个这样的图结构

    在这里插入图片描述

    很明显,该图为无向图,那么我们用矩阵的形式来表示它就如下图
    在这里插入图片描述
    图中的 0 表示该顶点无法通向另一个顶点,相反 1 就表示该顶点能通向另一个顶点

    先来看第一行,该行对应的是顶点A,那我们就拿顶点A与其它点一一对应,发现顶点A除了不能通向顶点D和自身,可以通向其它任何一个的顶点

    因为该图为无向图,因此顶点A如果能通向另一个顶点,那么这个顶点也一定能通向顶点A,所以这个顶点对应顶点A的也应该是 1

    为了大家更好的理解,我根据这个邻接矩阵,重新还原了一幅正确的图结构出来,如下面这张动图所示:

    在这里插入图片描述
    虽然我们确实用邻接矩阵表示了图结构,但是它有一个致命的缺点,那就是矩阵中存在着大量的0,这在程序中会占据大量的内存。此时我们思考一下,0就是表示没有,没有为什么还要写,所以我们来看一下第二种表示图结构的方法,它就很好的解决了邻接矩阵的缺陷

    (2)邻接表

    邻接表 是由每个顶点以及它的相邻顶点组成的

    还是使用刚才上面的那个例子,如图

    在这里插入图片描述
    那么此时我们的邻接表就是这样的,如下图

    在这里插入图片描述

    图中最左侧红色的表示各个顶点,它们对应的那一行存储着与它相关联的顶点

    因此,我们可以看出:

    • 顶点A 与 顶点B顶点C顶点E 相关联
    • 顶点B 与 顶点A 相关联
    • 顶点C 与 顶点A顶点D顶点E 相关联
    • 顶点D 与 顶点C 相关联
    • 顶点E 与 顶点A顶点C 相关联

    为了大家更好的理解,我根据这个邻接表,重新还原了一幅正确的图结构出来,如下面这张动图所示:

    在这里插入图片描述
    我们在文章末尾封装图结构时,也会用到这种表示方法

    四、遍历搜索

    在图结构中,存在着两种遍历搜索的方式,分别是 广度优先搜索深度优先搜索

    在介绍这两种搜索方式前,我们先来看一个例子

    在这里插入图片描述
    这是一个吃金币的小游戏,从入口开始,进去吃掉所到所有的金币,但是要尽可能少得走重复的路

    首先我们可以把它简化成我们学习的图结构,如图

    在这里插入图片描述
    接下来我们就根据这个图结构来介绍两种遍历搜索方式

    (1)广度优先搜索

    广度优先搜索 就是从第一个顶点开始,尝试访问尽可能靠近它的顶点,即先访问最靠近它的所有顶点,再访问第二靠近它的所有顶点,以此类推,直到访问完所有的顶点

    概念比较抽象,我们就拿上面的例子来说,如图所示

    在这里插入图片描述
    第一次先搜索离 顶点1 最近的两个顶点,即 顶点2顶点7

    然后再搜索离 顶点1 第二近的所有顶点,也就是离 顶点2顶点7 最近的所有顶点,如图所示
    在这里插入图片描述
    由图可知,离顶点2 最近的顶点为 顶点3顶点5 ,离 顶点7 最近的顶点为 顶点8 ,因此这几个点以此被遍历

    再继续往下搜索离 顶点1 第三近的所有顶点,也就是离 顶点3顶点5顶点8 最近的所有顶点,搜索过程如图所示
    在这里插入图片描述
    由图可知,离 顶点3 最近的顶点有 顶点6 ;离 顶点5 最近的顶点有 顶点4 ;离 顶点8 最近的顶点有 顶点9,因此它们也逐一被遍历

    到此为止,整个图结构就已经被遍历完成了,这就是一个广度优先搜索完整的过程

    (2)深度优先搜索

    深度优先搜索 就是从一个顶点开始,沿着一条路径一直搜索,直到到达该路径的最后一个结点,然后回退到之前经过但未搜索过的路径继续搜索,直到所有路径和结点都被搜索完毕

    同样的,概念比较抽象,我们来用上面的例子模拟一遍深度优先搜索,如图所示

    先随便沿着一条路径一直搜索,图中路径为 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 5 -> 4

    在这里插入图片描述

    当搜索到 顶点4 时,发现查找不到未被访问的顶点了,因此 顶点4 就是这条路径的最后一个顶点,此时我们要往后倒退,找寻别的每搜索过的路径

    此时发现当往后退到 顶点8 时,有一条路径上还有未被搜索过的顶点,即 8 -> 7 ,如图所示
    在这里插入图片描述

    沿着这条路径一直找到了最后一个顶点—— 顶点7,此时我们要继续往后退,看看还有没有别的路径没走过并且有未搜索过的顶点,但此时发现所有顶点都被访问过了,因此一个完整的深度优先搜索就完成了

    五、图结构的方法

    在封装图结构之前,我们先来了解一下图结构都由哪些方法,如下表所示

    方法 含义
    addVertex() 添加顶点
    addEdge() 添加边
    toString() 展示邻接表
    breadthFirstSearch() 广度优先搜索
    depthFirstSearch() 深度优先搜索

    六、用代码实现图结构

    前提:

    1. 我们封装的图结构中,存储边的方式用到的是我们上文提到的邻接表
    2. 封装的图结构面向的都是无权无向图

    (1)创建一个构造函数

    首先创建一个大的构造函数,用于存放二叉查找树的一些属性和方法。

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    }
    

    因为图结构是由顶点的集合和边的集合构成的,因此我们想要设定两个属性 vertexesedges ,分别存储着所有的顶点 、所有的边

    其中,属性 edges 是初始化了一个空对象。

    假设我们先新添加一个 顶点A ,那么我们除了在属性 vertexes 中存储一下该顶点信息,我们还要为 顶点A 在属性 edges 中创建一个键值对,键为 顶点A ,值是一个空数组,用于存放之后它的相邻顶点,如图所示

    在这里插入图片描述
    然后我们又新添加一个 顶点B ,并且设定 顶点A顶点B 为相邻顶点,那么此时的属性 edges 是这样的

    在这里插入图片描述
    此时可以很明显的看出,顶点A顶点B 相关联,即它们之间有一条边,它们互为相邻顶点

    (2)实现addVertex()方法

    addVertex() 方法就是将一个顶点添加到图结构中。该方法需要传入一个参数 v 用于表示顶点信息

    实现思路:

    1. 将新添加的顶点 v 添加到属性 vertexes
    2. 在属性 edges 中为顶点 v 创建一个数组空间,用于存放与其相关的边的信息

    我们来看一下代码

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    
    	// 方法
        // 添加顶点
        Graph.prototype.addVertex = function(v) {
            this.vertexes.push(v)
            this.edges[v] = []
        }
    }
    

    我们来使用一下该方法

    let graph = new Graph()
    
    graph.addVertex(3)
    graph.addVertex(9)
    graph.addVertex(5)
    

    我们来看一下我们定义的两个属性是什么样的,如图所示

    在这里插入图片描述

    在这里插入图片描述
    此时的各个顶点之间是没有任何的边的,等我们后面封装好了添加边的方法以后,再回头来看一下

    (3)实现addEdge()方法

    addEdge() 方法用于向图结构中添加边。该方法需要传入两个参数,即 v1v2,分别代表两个顶点

    实现思路:

    1. 找到属性 edges 中的 v1,为其添加一个相邻顶点 v1
    2. 同时找到属性 edges 中的 v2,为其添加一个相邻顶点 v1

    我们来看一下代码

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    
    	// 方法
        // 添加边
        Graph.prototype.addEdge = function(v1, v2) {
            this.edges[v1].push(v2)
            this.edges[v2].push(v1)
        }
    }
    

    现在我们来使用一下该方法

    let graph = new Graph()
    
    // 向图结构
    graph.addVertex(3)
    graph.addVertex(9)
    graph.addVertex(5)
    
    // 为顶点添加边
    // 在顶点3 和 顶点9 之间添加一条边
    graph.addEdge(3, 9)
    // 在顶点3 和 顶点5 之间添加一条边
    graph.addEdge(3, 5)
    // 在顶点5 和 顶点9 之间添加一条边
    graph.addEdge(5, 9)
    

    我们来看一下我们定义的两个属性是什么样的,如图所示
    在这里插入图片描述
    在这里插入图片描述
    此时的图结构是这样的

    在这里插入图片描述

    (4)实现toString()方法

    toString() 方法是用字符串的形式来向我们展示邻接表。该方法无需传入参数

    我们先来看一下我们最终需要的展示效果是如何的,如图

    在这里插入图片描述
    其实就是依次展示了每个顶点的所有相邻顶点

    实现思路:

    1. 创建一个字符串 str
    2. 遍历属性 vertexes,获取到每个顶点
    3. 每获取到一个顶点时,添加到 str 中,然后从属性 edges 中找到存放该顶点的相邻顶点的数组,然后遍历该数组,将所有相邻顶点添加到 str
    4. 最终返回 str

    我们直接来看一下代码

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    
    	// 方法
        // 展示邻接表
        Graph.prototype.toString = function() {
        	// 1. 创建字符串,用于存放数据
            let string = ''
            
            // 2. 遍历所有顶点
            for(let i in this.vertexes) {
    			
    			// 2.1 获取遍历到的顶点
                let vertex = this.vertexes[i]
    			
    			// 2.2 将遍历到的顶点添加到字符串中
                string += `${vertex} => `
                
                // 2.3 获取存储该顶点所有的相邻顶点的数组
                let edges = this.edges[vertex]
    
    			// 2.4 遍历该顶点所有的相邻顶点
                for(let i in edges) {
                	// 2.4.1 将遍历到的相邻顶点添加到字符串中
                    string += `${edges[i]} `
                }
                // 2.5 换行
                string += '\n'
            }
    		
    		// 3. 返回最终结果
            return string
        }
    }
    

    我们来使用一下该方法,为了方便,这里仍用上面的例子

    let graph = new Graph()
    
    // 向图结构
    graph.addVertex(3)
    graph.addVertex(9)
    graph.addVertex(5)
    
    // 为顶点添加边
    graph.addEdge(3, 9)
    graph.addEdge(3, 5)
    graph.addEdge(5, 9)
    
    // 获取邻接表
    console.log(graph.toString())
    /* 返回结果为:
    				3 => 9 5 
    				9 => 3 5 
    				5 => 3 9 
    */
    

    核对了一下,结果时正确的

    (5)实现initColor()方法(内部方法)

    在封装 breadthFirstSearch()方法和 depthFirstSearch() 方法之前,我们要额外封装一个 initColor()方法,这里要用到一个思想,但上面在介绍广度优先搜索和深度优先搜索时没有提到,这里我们来了解一下

    无论是在进行广度优先搜索还是深度优先搜索时,我们搜索顶点的时候,会频繁地重复搜索到某些顶点,那么我们就要用一种方式,使被搜索过的顶点不再被重复搜索一次。这种方法就是给每个顶点一个颜色标记,没有被搜索过的顶点被标记白色,被搜索过的顶点被标记黑色

    我们就拿一个简单的广度优先搜索的例子,来感受一下该方法的作用

    首先是广度优先搜索的例子,如图所示

    在这里插入图片描述
    首先我们从 顶点A 开始搜索,先依次遍历其所有的相邻顶点有 顶点B顶点C

    然后接着分别遍历 顶点B顶点C 的所有相邻顶点,其中 顶点B 的所有相邻顶点有 顶点A顶点C顶点D顶点C 的所有相邻顶点有 顶点A顶点B顶点D ,我们就按上述顺序依次遍历。此时我们可以发现,当遍历 顶点B 的相邻顶点时,会搜索到 顶点A,但是 顶点A 是我们一开始就搜索过的,因此不应该重复遍历。

    同样的,当遍历完 顶点B 的相邻顶点以后,在遍历 顶点C 的相邻顶点时,我们会发现其所有的相邻顶点之前都已经搜索过了,现在不应该重复遍历了。

    所以我们来看一下使用了颜色标记以后的搜索过程吧

    首先遍历到初始顶点——顶点A,此时我们给它标记黑色

    在这里插入图片描述
    接着遍历 顶点A 所有的相邻顶点,即 顶点B顶点C,并将它们都标记为黑色

    在这里插入图片描述
    最后,我们要遍历 顶点B顶点C 所有的相邻顶点

    先遍历 顶点B 的相邻顶点,分别是 顶点A顶点C顶点D,我们通过颜色辨认得知 顶点A顶点C 都为黑色,表示已经被搜索过了,所以无需重复遍历它们,此时只有 顶点D 不为黑色,所以我们搜索到了 顶点D,并将其标记为黑色

    在这里插入图片描述
    接着我们要遍历 顶点C 的相邻顶点,分别为 顶点A顶点B顶点D,但我们此时通过颜色辨认发现,所有的相邻顶点都被搜索过了,因此无需重复遍历这些顶点了。

    这样一个完美的广度优先搜索就完成了。

    因此,我们需要封装一个颜色初始化的函数,用于将所有顶点的颜色都初始化为白色,并将颜色信息存放在一个对象中,返回该对象用于别的函数

    我们来看一下代码

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    
    	// 方法
        // 顶点颜色初始化(内部函数)
        Graph.prototype.initColor = function() {
            // 1. 创建对象,存放颜色信息
            let color = {}
            
            // 2. 遍历所有顶点,将其颜色初始化为白色
            for(let i in this.vertexes) {
                color[this.vertexes[i]] = 'white'
            }
    		
    		// 3. 返回颜色对象
            return color       
        }
    }
    

    该方法的使用我们会在后续使用到,这里就不做演示了

    (6)实现breadthFirstSearch()方法

    breadthFirstSearch() 方法是对图结构进行广度优先搜索。该方法接收两个参数,第一个参数为初始顶点,即从哪个顶点开始搜索;第二个参数接收一个回调函数 handle 作为参数,用于在搜索过程中进行一些操作

    在上文多次介绍了广度优先搜索,其实这是一种基于队列来搜索顶点的方式

    注: 这里我就把我之前文章中封装的队列构造函数直接拿来使用了,如果想看队列的各个方法的实现过程的小伙伴可以点击下面跳转链接进行查看

    【数据结构与算法】详解什么是队列,并用代码手动实现一个队列结构

    实现思路:

    1. 先将所有的顶点颜色初始化为白色
    2. 从给定的第一个顶点开始搜索,即将第一个顶点添加到队列中,并将第一个顶点标记为黑色
    3. 从队列中取出一个顶点,查找该顶点的未被访问过的相邻顶点,将其添加到队列的队尾位置,并将这些顶点标记未黑色,表示也被访问过
    4. 执行我们的回调函数 handle,将该顶点作为参数传入
    5. 一直循环 步骤3 ~ 步骤4 ,直到队列为空

    我们来看一下具体的代码

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    
    	// 已经封装好的队列构造函数
    	function Queue() {
    	    this.list = []
    	
    	    //入队列
    	    Queue.prototype.enqueue = function (e) {
    	        this.list.push(e)
    	    }
    	    //出队列
    	    Queue.prototype.dequeue = function () {
    	        return this.list.shift()
    	    }
    	    //判断队列是否为空
    	    Queue.prototype.isEmpty = function() {
    	        if(this.list.length === 0) {
    	            return true
    	        }
    	        else {
    	            return false
    	        }
    	    }
    	    //返回队列中元素个数
    	    Queue.prototype.size = function () {
    	        return this.list.length
    	    }
    	    //返回队列中的第一个元素
    	    Queue.prototype.front = function () {
    	        return this.list[0]
    	    }
    	    //返回当前队列
    	    Queue.prototype.toString = function () {
    	        let string = ''
    	        for(let i in this.list) {
    	            string += `${this.list[i]} `
    	        }
    	        return string
    	    }
    	}
    
    	// 方法
        // 顶点颜色初始化(内部函数)
        Graph.prototype.initColor = function() {
            // 1. 创建对象,存放颜色信息
            let color = {}
            
            // 2. 遍历所有顶点,将其颜色初始化为白色
            for(let i in this.vertexes) {
                color[this.vertexes[i]] = 'white'
            }
    		
    		// 3. 返回颜色对象
            return color       
        }
    
    	// 广度优先搜索
        Graph.prototype.breadthFirstSearch = function(firstVertex, handle) {
            // 1. 初始化所有顶点颜色
            const color = this.initColor()
            
            // 2. 新建一个队列
            const queue = new Queue()
            
            // 3. 将第一个顶点加入队列
            queue.enqueue(firstVertex)
    
            // 4. 开始广度优先搜索
            while(!queue.isEmpty()) {
    
                // 4.1 从队列中取出一个顶点
                let vertex = queue.dequeue()
    
                // 4.2 获取与该顶点相关的其他顶点
                let otherVertexes = this.edges[vertex]
    
                // 4.3 将该顶点设为黑色,表示已被访问过,防止后面重复访问
                color[vertex] = 'black'
    
                // 4.4 遍历与该顶点相关的其它顶点
                for(let i in otherVertexes) {
    
                    // 4.4.1 获取与该顶点相关的顶点
                    let item = otherVertexes[i]
    
                    // 4.4.1 若未被访问,则加入到队列中
                    if(color[item] === 'white') {
                        color[item] = 'black'
                        queue.enqueue(item)
                    }
                }
    
                // 4.5 执行我们的回调函数
                handle(vertex)
            }     
        }
    }
    

    我们来使用一下该方法吧,为了方便检查函数的正确性,我们之前介绍到的吃金币的例子,并且回调函数 handle 用来打印一下访问到的顶点

    这里我直接把正确的访问顺序图放在这里,方便大家下面核对结果是否正确
    在这里插入图片描述

    let graph = new Graph()
    
    graph.addVertex(1)
    graph.addVertex(2)
    graph.addVertex(3)
    graph.addVertex(4)
    graph.addVertex(5)
    graph.addVertex(6)
    graph.addVertex(7)
    graph.addVertex(8)
    graph.addVertex(9)
    
    graph.addEdge(1, 2)
    graph.addEdge(1, 7)
    graph.addEdge(2, 3)
    graph.addEdge(2, 5)
    graph.addEdge(3, 2)
    graph.addEdge(3, 6)
    graph.addEdge(4, 5)
    graph.addEdge(5, 4)
    graph.addEdge(5, 2)
    graph.addEdge(5, 8)
    graph.addEdge(6, 3)
    graph.addEdge(6, 9)
    graph.addEdge(7, 1)
    graph.addEdge(7, 8)
    graph.addEdge(8, 5)
    graph.addEdge(8, 7)
    graph.addEdge(8, 9)
    graph.addEdge(9, 6)
    graph.addEdge(9, 8)
    
    // 广度优先搜索
    graph.breadthFirstSearch(1, function(vertex) {
    	// 打印访问到的顶点
    	console.log(vertex)
    })
    /* 打印结果:
    			1
    			2
    			7
    			3
    			5
    			8
    			6
    			4
    			9
    */
    

    把打印的结果和图片核对以后发现结果是一致的,因此这个方法是没有问题的

    (7)实现depthFirstSearch()方法

    depthFirstSearch() 方法是对图结构进行深度优先搜索。该方法接收两个参数,第一个参数为初始顶点,即从哪个顶点开始搜索;第二个参数接收一个回调函数 handle 作为参数,用于在搜索过程中进行一些操作

    在上文多次介绍了深度优先搜索,其实这是一种基于来搜索顶点的方式,我们也直到其实递归也是利用栈结构的思路实现的,因此我们这里封装该方法时就不把之前封装好的栈结构拿来使用了,直接利用递归实现,正好递归也能把代码变得简洁点

    因此首先我们要封装一个递归调用的主体函数,方法名为 depthVisit,该方法接收三个参数,第一个参数为搜索的顶点;第二个参数为存储顶点颜色信息的对象;第三个参数为回调函数,实现思路如下

    depthVisit()方法的实现思路:

    1. 从给定的顶点开始搜索,将其标记为黑色,表示已被访问过
    2. 执行我们的回调函数 handle,将该顶点作为参数传入
    3. 遍历该顶点的所有相邻顶点,若相邻顶点为黑色,则表示已被访问过,就不做任何处理
    4. 若相邻顶点为白色,则表示未被访问,于是就再次调用 breadthFirstSearch()方法,将该顶点作为第一个参数

    再来简单说一下 depthFirstSearch() 方法的实现思路

    depthFirstSearch()方法的实现思路:

    1. 将所有顶点的颜色初始化为白色
    2. 选择一个顶点作为深度优先搜索的第一个顶点,调用 depthVisit()方法,并将该顶点作为该方法的第一个参数

    接下来我们来看一下具体的代码吧

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    
    	// 方法
        // 顶点颜色初始化(内部函数)
        Graph.prototype.initColor = function() {
            // 1. 创建对象,存放颜色信息
            let color = {}
            
            // 2. 遍历所有顶点,将其颜色初始化为白色
            for(let i in this.vertexes) {
                color[this.vertexes[i]] = 'white'
            }
    		
    		// 3. 返回颜色对象
            return color       
        }
    	
    	// 深度优先搜索
        Graph.prototype.depthFirstSearch = function(firstVertex, handle) {
            // 1. 初始化所有顶点颜色
            const color = this.initColor()
    
            // 2. 开始递归访问各个顶点
            this.depthVisit(firstVertex, color, handle)
        }
    
        // 深度优先搜索的递归访问(内部函数)
        Graph.prototype.depthVisit = function(vertex, color, handle) {
            // 1. 先将访问到的顶点颜色设为黑色,防止后面重复访问
            color[vertex] = 'black'
    
            // 2. 执行回调函数
            handle(vertex)
    
            // 3. 获取与该顶点相关的其它顶点
            let otherVertexes = this.edges[vertex]
    
            // 4. 遍历所有相关的顶点
            for(let i in otherVertexes) {
                let item = otherVertexes[i]
                // 4.1 访问没有被访问过的相邻顶点
                if(color[item] === 'white') {
                    this.depthVisit(item, color, handle)
                }
            }
    
        }
    	
    }
    

    同样的,我们也用上文将到的吃金币例子中的深度优先搜索的结果图来验证我们方法的正确性,图片如下

    在这里插入图片描述

    let graph = new Graph()
    
    graph.addVertex(1)
    graph.addVertex(2)
    graph.addVertex(3)
    graph.addVertex(4)
    graph.addVertex(5)
    graph.addVertex(6)
    graph.addVertex(7)
    graph.addVertex(8)
    graph.addVertex(9)
    
    graph.addEdge(1, 2)
    graph.addEdge(1, 7)
    graph.addEdge(2, 3)
    graph.addEdge(2, 5)
    graph.addEdge(3, 2)
    graph.addEdge(3, 6)
    graph.addEdge(4, 5)
    graph.addEdge(5, 4)
    graph.addEdge(5, 2)
    graph.addEdge(5, 8)
    graph.addEdge(6, 3)
    graph.addEdge(6, 9)
    graph.addEdge(7, 1)
    graph.addEdge(7, 8)
    graph.addEdge(8, 5)
    graph.addEdge(8, 7)
    graph.addEdge(8, 9)
    graph.addEdge(9, 6)
    graph.addEdge(9, 8)
    
    // 深度优先搜索
    graph.depthFirstSearch(1, function(vertex) {
    	// 打印访问到的顶点
    	console.log(vertex)
    })
    /* 打印结果:
    			1
    			2
    			3
    			6
    			9
    			8
    			5
    			4
    			7
    */
    

    把打印的结果和图片核对以后发现结果是一致的,因此这个方法是没有问题的

    七、结束语

    图结构的讲解就到这里了,希望大家对图结构有了更深一层的理解。到此为止,我的【数据结构与算法】专栏中的数据结构部分已经结束了,接下来准备开始讲解排序算法了,下一篇文章为基本排序算法,顺便会在文中介绍一下大O表示法

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

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

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

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

    展开全文
  • 详细展示RNN的网络结构

    万次阅读 2018-09-17 20:27:54
    下面简单介绍一下RNN的结构,如果简略地去看,RNN结构很简单,根本没有CNN那么复杂,但是要具体实现,还是需要仔细思考一下,希望本篇博客能把RNN结构说的明白。 循环神经网络(Recurrent Neural Network,RNN)DNN...

    下面简单介绍一下RNN的结构,如果简略地去看,RNN结构很简单,根本没有CNN那么复杂,但是要具体实现,还是需要仔细思考一下,希望本篇博客能把RNN结构说的明白。

    循环神经网络(Recurrent Neural Network,RNN)DNN以及CNN在对样本提取特征的时候,样本与样本之间是独立的,而有些情况是无法把每个输入的样本都看作是独立的,比如NLP中的此行标注问题,ASR中每个音素都和前一个音素是相关的,这类问题可以看做一种带有时序序列的问题,无法将样本看做是相互独立的,因此单纯的DNN和CNN解决这类问题就比较棘手。此时RNN就是一种解决这类问题很好的模型。

     由上图可以看出,RNN的结构是一个重复的过程,且权重W,U,V是共享的,这也是借鉴了CNN的思想,可以减少参数量,从而减少计算的复杂度。t时刻隐藏层的输出需要t-1时刻的隐藏层的输出,RNN以此来实现信息的传递。如果上图计算不清晰,就请看下面的两幅图片。

     看到这两幅图已经很清晰地展示了RNN的整体结构,但是在具体实现的时候,或者你需要了解每一个细节,我们知道在图像处理的时候,我们的每一个图像被拉成一个向量,每一个像素其实就是输入层的一个神经元。并且对于隐藏层每个神经元同样相当于一个特征图所构成向量的一个像素值。所以,上述的隐藏层并不是一个单一的神经元,它是一个包含多个神经元的隐藏层,如下图所示。这才是RNN的真正的结构。

    好了,上面只是RNN的图形描述,现在用公式的形式来对RNN的前向传播进行描述,以下图的符号进行描述,很容易就可以写出前向传播的公式。

    公式符号表
    符号 含义

    K

    输入向量的大小(one-hot长度,也是词典大小)

    T

    输入的每一个序列的长度

    H

    隐藏层神经元的个数

    X=\left \{ x_{1},x_{2},x_{3}....,x_{T} \right \}

    样本集合

    x_{t}\epsilon \mathbb{R}^{K\times 1}

    t时刻的输入

    y_{t}\epsilon \mathbb{R}^{K\times 1}

    t时刻经过Softmax层的输出。

    \hat{y}_{t}\epsilon \mathbb{R}^{K\times 1}

    t时刻输入样本的真实标签

    L_{t}

    t时刻的损失函数,使用交叉熵函数,

    L_t=-\hat{y}_t^Tlog(y_t)

    L

    序列对应的损失函数:

    L=\sum\limits_t^T L_t

    RNN的反向传播是每处理完一个样本就需要对参数进行更新,因此当执行完一个序列之后,总的损失函数就是各个时刻所得的损失之和。

    s_{t}\epsilon \mathbb{R}^{H\times 1}

    t个时刻RNN隐藏层的输入。

    h_{t}\epsilon \mathbb{R}^{H\times 1}

    第t个时刻RNN隐藏层的输出。

    z_{t}\epsilon \mathbb{R}^{H\times 1}

    输出层的输入,即Softmax函数的输入

    W\epsilon \mathbb{R}^{H\times K}

    输入层与隐藏层之间的权重。

    U\epsilon \mathbb{R}^{H\times H}

    上一个时刻的隐藏层 与 当前时刻隐藏层之间的权值。

    V\epsilon \mathbb{R}^{K\times H}

    隐藏层与输出层之间的权重。

    RNN的前向传播过程:  

                                                                                 \begin{matrix} \: \: \: \: \: \: \: \: \; \; \; \; \; \; \; \; \; \; \; \; \; s_t=Uh_{t-1}+Wx_t+b\\ \\ h_t=\sigma(s_t)\\ \\ \; \; \; \; z_t=Vh_t+c\\ \\ \; \; \; \; \; \; \; \; \; \; y_t=\mathrm{softmax}(z_t) \end{matrix}

    但是RNN,与CNN或者DNN相比,其参数更新是如何实现的呢?这是训练RNN的一个核心问题。请看下篇BPTT。

     

    参考:

            李宏毅老师课件

    展开全文
  • IDEA 树形展示包结构

    千次阅读 2019-04-26 16:39:16
    IDEA 编辑器默认的包结构如图 在这样的包结构上创建文件夹非常不方便,将其更改为树形结构步骤如下 点击图中设置图标 将Compact MiddlePackages 的勾去掉,如果是第一次修改此处显示的应该是...

    IDEA 编辑器默认的包结构如图

    在这样的包结构上创建文件夹非常不方便,将其更改为树形结构步骤如下

    点击图中设置图标

    将 Compact Middle Packages 的勾去掉,如果是第一次修改此处显示的应该是 Hide Empty Middle Packages

    我这里的示例是已经修改过的,所以是 Compact Middle Packages

    修改后如下图,树形展示包结构

     

    展开全文
  • 本文将来讲解一下一种常见的线性数据结构—链表,因为链表和数组一样都是一种线性的数据结构,但是它俩的实现原理是完全不同的,所以在讲解链表之前,我们来回顾一下 数组 结构

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

    本文将来讲解一下一种常见的线性数据结构—链表,因为链表和数组一样都是一种线性的数据结构,但是它俩的实现原理是完全不同的,所以在讲解链表之前,我们来回顾一下数组结构。

    数组 几乎是每一种编程语言中都自带的一种常用的数据存储结构,我们可以很方便的通过下标值来获取到我们想要的数组中的元素。

    但是数组也还是有很大的缺点的,例如现在有一个长度为10的数组,那么数组中的每个元素都对应着各自的下标值,范围为 0~9 ,现在我们要往下标值为 2 的位置插入一个新的元素,我们需要做的就是先把数组的长度变成11,然后将数组中原本下标值为 2 以及之后的所有元素都向后移动一个位置,即下标值 +1,最后再将我们要插入的新元素放到下标值为 2 的位置。

    同样的,如果我们要删除数组中的某个元素,也是一样的道理,先删除要删除的元素,然后把被删除元素后面的所有元素往前移动一个位置,即下标值 -1,最后把数组的长度 -1

    由上面两个例子可以看出,数组的 添加元素删除元素 非常消耗性能,可谓牵一发而动全身,这就是数组最大的缺点,所以 链表 的出现就弥补了数组的这一缺点。本文就来详细讲解一下链表的概念以及如何实现一个链表。

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

    在这里插入图片描述

    一、什么是链表

    上面刚提到,链表 弥补了数组的一些缺点,那么是如何做到的呢?链表到底是什么样的呢?接下来我们就用一个简单的例子来解释一下链表的概念

    假设在一个教室中,所有学生的座位都排成一列,这一列就可以看成是一个 链表,如图所示
    在这里插入图片描述
    每个座位上坐着的学生就相当于链表中的一个 元素 。假如老师记性不好,学生记性也不好,所以他们就很难记住自己的座位到底是哪一个。因此老师想了一个好办法,老师就只记住座位的第一个是谁,然后每一个学生都只要记住自己的后桌是谁就好了。

    每次刚进教室准备找座位坐下,老师就告诉学生们说,小5 是坐在第一个的,然后 小5 记得他的后桌是 小1,于是 小1 也找到了座位坐下,因为 小1 记得他的后桌是 小8,所以 小8 也找到自己的座位了……以此类推,一直到坐在最后一个的 小2,就这样大家就都可以找到自己的座位了,如图:
    在这里插入图片描述
    有一天, 小8 同学要转学了,所以座位有变动,为了保证座位不空着,小8 走了以后,把他的座位也搬走,以免占用教室空间。此时要让其余同学仍然能正确找到自己的座位的方式就很简单,那就是让原本 小8 的前桌记住,他现在的后桌是 小6了,不再是 小8 了,所以现在的情况如图所示:
    在这里插入图片描述
    像这样的记忆自己座位的方式非常的好,因为一个同学转学,只需要让一个人重新记忆自己的后桌是谁即可,而不需要让所有的同学重新记忆。

    同理,比如突然有一天,有一个新同学 小7 到了这个班级,老师安排她坐在 小5 后面,此时 小5 就需要记住,他的后桌换成了 小7,而这个新来的同学 小7 也像其他同学一样要记住自己的后桌为 小1,此时的情况是这样的,如图:
    在这里插入图片描述
    同样的,新来一个同学造成的位置变动,只让一个同学重新记忆自己的后桌是谁,还同时让新来的同学记住自己的后桌是谁,而没有让所有的同学全部重新记忆,这无疑是一个非常高效的方式。

    例子讲完了,接下来进入正题,链表 的实现就像我们刚才讲的那个例子。在链表中,每一个元素都包含两个属性,即 该元素的值item下一个元素next,其中,item 就像我们刚才例子中的同学;next 就像同学记住的他们的后桌是谁。同时链表中有一个指针 head 指向链表第一个元素,这个 head 就好比老师记住的坐在第一个的是谁。

    接下来我们来看一下链表的结构
    在这里插入图片描述
    这整体看上去就像一个链子,所以叫做链表,每一个 itemnext 组合起来称作是一个元素,再补充一下,最后一个元素指向 null,就相当于例子中坐在最后一个的同学说他没有后桌一样。

    此时我们要删除第二个元素,链表结构就会变成这个样子
    在这里插入图片描述
    大家可以根据这个结构比对一下刚刚我举得例子,好好理解一下链表的结构形式和实现原理。

    二、链表的方法

    因为链表是弥补数组缺点而形成的一种数据结构,所以链表也有像数组一样多的方法,这里我们就来看一下链表都有哪些方法吧

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

    三、用代码实现链表

    根据上面对链表的讲解,我们知道,我们无论是要删除元素还是添加元素,每次都是要从 head 开始,依次往后查找元素,所以对于链表的每一个方法,我们每次做的就是从 head 开始遍历,并通过 next 找到每一个元素的下一个元素是谁。

    (1)创建一个构造函数

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

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

    其中定义了属性 head,并赋值了一个 null,表示现在链表内没有元素;而属性 length则是为了储存链表内的元素个数,这是为了提高链表一些方法的性能,例如之后要写的 size()方法,我们每次调用该方法时,都要遍历整个链表,然后统计元素个数,那么还不如有一个属性记录着元素个数,只需要在添加元素的方法里给 length + 1,在删除元素的方法里给 length - 1

    (2)创建内部构造函数

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

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    }
    

    之后要如果要添加新元素,我们只需要 new Node(item),并把元素的值传入就可以创建一个元素的实例对象了,这里默认是给每个新创建的元素实例的 next 属性设置为 null,是因为刚开始我们并不知道它被添加到链表里以后,后一个元素是谁,当然,我们只需要在知道了后一个元素是谁的情况下设置一下这个属性即可。

    (3)实现append()方法

    append()方法就是将元素添加到链表的最后一个。

    实现思路:

    1. 创建新的元素实例对象 node
    2. 判断 length 是否为0,若为0,则直接将 head 指向 node
    3. length 不为0,则根据每个元素的 next 属性遍历链表
    4. 若元素的 next 的值不等于 null,继续遍历
    5. 若元素的 next 的值等于 null,则表示已经查找到链表的最后一个元素,所以直接将该元素的 next 值设置成 node 即可
    6. 属性 length + 1

    为了方便你们理解这个实现思路,我做了个动图展示一下思路
    在这里插入图片描述
    在这里插入图片描述
    思路讲完了,我们直接来看代码

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//在链表尾部追加元素
    	LinkedList.prototype.append = function (item) {
    		// 1.创建新的元素实例对象
            let node = new Node(item)
            
            // 2.判断链表是否为空
            if(this.length === 0) {
                this.head = node
            }
            else {
                let current = this.head
                // 3.遍历链表,找到最后一个元素
                while(current.next) {
                    current = current.next
                }
                // 4.将我们要添加的元素赋值给原本链表中的最后一个元素
                current.next = node
            }
    		
    		//链表元素+1
            this.length ++
        }
    }
    

    我们来使用一下该方法

    刚开始的链表是这个样子的
    在这里插入图片描述
    然后我们使用一下 append()方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    

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

    (4)实现insert()方法

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

    实现思路:

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

    为了方便你们理解这个实现思路,我做了个动图展示一下思路
    在这里插入图片描述
    在这里插入图片描述
    思路讲完了,我们直接来看代码

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//在某个位置插入新的元素
        LinkedList.prototype.insert = function (position, item) {
        	// 1.创建新的元素实例对象
            let node = new Node(item)
            
    		// 2.判断是否越界
            if(position < 0 || position > this.length) return false
            
            // 3.判断插入的位置是否为 0
            if(position === 0) {
                node.next = this.head
                this.head = node
            }
            else {
            	// 4.遍历链表,找到索引等于position的元素
                let current = this.head
                let prev = null
                let index = 0
                while (index++ < position) {
                    prev = current
                    current = current.next
                }
        		// 5.插入元素
                prev.next = node
                node.next = current
        
            }
            // 6.链表元素 +1
            this.length ++
            return true
            
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.insert(1, 'c++')
    

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

    (5)实现get()方法

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

    实现思路:

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

    接下来我们来单独实现一下该方法

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//获取对应位置的元素
        LinkedList.prototype.get = function (position) {
        	// 1.判断是否越界
            if(position < 0 || position >= this.length) return false
            
    	        let current = this.head
    	        let index = 0
    	        // 2.遍历链表,直到 index == position
    	        while (index++ < position) {
    	            current = current.next
    	        }
    	        // 3.返回当前索引位置的元素
    	        return current.item
            
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.get(2)            //返回 java
    

    (6)实现indexOf()方法

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

    因为比较简单,这里就不讲解思路了,我们直接用代码来实现这个方法

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//获取元素的索引
        LinkedList.prototype.indexOf = function (item) {
            let current = this.head
            let index = 0
            while (index < this.length) {
                if(current.item === item) {
                    return index
                }
                else {
                    current = current.next
                    index ++
                }
            }
            return -1
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.indexOf('python')    //返回 1
    linkedlist.indexOf('c++')       //返回 -1
    

    (7)实现update()方法

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

    这里就简单讲下思路吧,首先要先判断 position 是否越界,若越界直接返回 false表示修改失败,若没有越界就遍历链表,同时记录当前索引 index,当 index == position时,就将当前索引位置上的元素的值 item修改成 NewItem

    接下来我们来单独实现一下该方法

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//修改某位置上的元素
        LinkedList.prototype.update = function (position, NewItem) {
        	// 1.判断是否越界
            if(position < 0 || position >= this.length) return false
            else {
                let current = this.head
                let index = 0
                
                // 2.遍历链表,找到索引等于position的元素对象
                while (index < position) {
                    current = current.next
                    index ++
                }
                
                // 3.将索引等于position的元素的值改为NewItem
                current.item = NewItem
                return true
            }
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.update(2, 'c++') 
    

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

    (8)实现removeAt()方法

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

    实现思路:

    1. 判断 position 是否越界,若越界,则直接返回 false 表示移除元素失败
    2. 若没有越界,判断 position 是否等于 0,若等于 0,则直接将链表第一个元素的 next 值赋值给 head,然后 length - 1
    3. position 不等于 0,则遍历链表,同时记录当前索引 index,遍历的当前元素 currentcurrent的上一个元素 prev
    4. index === position时,则将 currentnext 值赋值给 prevnext 值即可,同时 length - 1

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

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//移除某位置上的元素
        LinkedList.prototype.removeAt = function (position) {
        	// 1.判断是否越界
            if(position < 0 || position >= this.length) return false
            
            let current = this.head
            let prev = null
            let index = 0
            
            // 2.判断position是否等于 0
            if(position === 0) {
                this.head = current.next
            }
            else {
            	// 3.遍历链表
                while (index < position) {
                    prev = current
                    current = current.next
                    index ++
                }
                // 4.移除对应元素
                prev.next = current.next
            }
    		
    		// 5.链表元素 -1
            this.length --
            return true
            
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.removeAt(2)    //返回  true
    linkedlist.removeAt(3)    //返回  false,表示删除失败
    

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

    (9)实现remove()方法

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

    实现思路:

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

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

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//移除某元素
        LinkedList.prototype.remove = function (data) {
        	// 1.获取data在链表中的索引
            let index = this.indexOf(data)
    		
    		// 2.利用removeAt()方法删除链表中的data
            this.removeAt(index)
    		
    		// 3.返回被删除元素data在链表中的索引
    		return index
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.remove('javascript')    //返回 0
    

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

    (10)实现isEmpty()方法

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

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

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

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//判断链表是否为空
        LinkedList.prototype.isEmpty = function () {
            if(this.length === 0) {
                return true
            }
            else {
                return false
            }
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.isEmpty()          //返回 true,此时链表中无元素
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.inEmpty()         //返回 false,此时链表中有三个元素
    

    (11)实现size()方法

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

    我们来实现一下该方法

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//返回链表的元素个数
        LinkedList.prototype.size = function () {
            return this.length
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.size()          //返回 0,此时链表中无元素
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.size()         //返回 3,此时链表中有三个元素
    

    (12)实现toString()方法

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

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

    我们来实现一下该方法

    function LinkedList() {
        //属性
        this.head = null
        this.length = 0
    
        //每个元素的定义类
        function Node(item) {
            this.item = item
            this.next = null
        }
    	
    	//展示整个链表
        LinkedList.prototype.toString = function () {
            let string = ''
            let current = this.head
            while (current) {
                string += `${current.item} `
                current = current.next
            }
            return string
        }
    }
    

    我们来使用一下该方法

    let linkedlist = new LinkedList()
    
    linkedlist.append('javascript')
    linkedlist.append('python')
    linkedlist.append('java')
    
    linkedlist.toString()           //返回 javascript python java
    

    四、总结

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

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

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

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

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

    展开全文
  • 如上 方便同时查看更多的内容 这里可以选择显示 目录(projects) 或 类的结构(structure) 显示之后进行如下的设置即可
  • 什么是蛋白质结构域?什么是HTH?

    千次阅读 2020-09-09 12:56:17
    1. 什么是蛋白质结构域? 结构域是蛋白质三维结构中小的保守区域,展示了蛋白质功能的属性,是构成蛋白质(三级)结构的基本单元,结构域检测是蛋白质分类和功能注释的重要方面。 蛋白质结构域与蛋白质完成生理功能...
  • 结构是一种非常常见的数据结构,并且在很多场景下也被用到。其实栈结构跟数组结构很像,只是在数组的基础...数据结构——栈一、什么是栈二、栈结构的方法三、用代码实现一个栈结构(1)创建一个构造函数(2)实现push
  • 队列结构也是平时非常常见的一种受限的线性数据结构。它跟栈结构一样都是受限的数据结构,区别就是...数据结构——队列一、什么是队列二、队列结构的方法三、用代码实现一个队列结构(1)创建一个构造函数(2)实现enq
  • 集合这个概念应该大家在学习数学的时候都听过并且有学习过,它也是一种数据结构,我们还是需要用代码来实现集合的很多方法。 学习过ES6语法的小伙伴应该知道,ES6新增了一种 Set 数据结构,这就是集合,尽管官方已经...
  • 多层级部门结构展示与分级汇总

    千次阅读 2019-08-15 11:15:47
    报表设计中,经常涉及层次结构的数据,比如产品的多级分类、组织的多级部门。如何展示层级结构本身,并分级汇总相关的数值数据,是报表设计人员经常面对的挑战。 下面是一个典型的部门表: 层级关系的关键是...
  • angularjs 递归 展示树状结构

    千次阅读 2017-07-27 17:17:26
    {{item.cateName}} 5. 5.
  • eclipse项目目录展示结构设置

    千次阅读 2019-09-29 13:47:43
    常用的目录展示结构 而修改的方式很简单,步骤如下 1.鼠标移动到下图圈起来的位置 2.移动到选项Projects Presentation 3.选择选项Hierarchical
  • python数据结构-树的列表展示

    千次阅读 2018-07-12 11:35:34
    列表表示 在由列表表示的树中,我们将从 Python 的列表数据结构开始,并编写上面定义的函数。虽然将接口作为一组操作在列表上编写与我们实现的其他抽象数据类型有点不同,但这样做是有趣的,因为它为我们提供了一个...
  • JSTL实现递归展示树型结构数据

    千次阅读 2015-12-22 16:43:52
    一个树型结构的数据在数据库里 映射为对象Tree(id, name, url....), Tree添加了一个自描述的属性List children 从数据库中根据根节点,递归出树结构放到List treeList中,现在要求在显示中按层级显示: ...
  • 展示表结构 show create table + 表名

    万次阅读 2019-01-04 11:24:03
      展示ddl CREATE TABLE `crm_dictionary` (  `id` bigint(20) NOT NULL AUTO_INCREMENT,  `code` int(16) NOT NULL,  `value` varchar(256) NOT NULL,  `type` varchar(32) NOT NULL, ...
  • JSTL实现递归展示树型结构数据!

    万次阅读 2012-07-30 13:55:28
    一个树型结构的数据在数据库里 映射为对象Tree(id, name, url....), Tree添加了一个自描述的属性List children 从数据库中根据根节点,递归出树结构放到List treeList中,现在要求在显示中按层级显示: ...
  • ztree树形结构展示

    千次阅读 2017-12-21 14:13:45
    var treeObj = $.fn.zTree.getZTreeObj("menuTree");//获取树对象 //获取全部节点数据 var nodes = treeObj.getNodes(); //var nodes = treeObj.transformToArray(treeObj.getNodes());
  • 微信小程序文件夹目录结构显示 最近做微信小程序,碰到列表展示客户信息。含有二级目录,想做成资源管理器那种加减号显示文件目录。找了好久小程序官方文档,没有找到百度也没有,只能自己琢磨了,还好做出来了。多...
  • IDEA中project展示树形结构

    千次阅读 2018-05-27 10:09:00
    首先将项目导入到IDEA中,设置SDK,我的web项目的sdk即为设置jdk,然后点击view-&gt;ToolWindows-&gt;project,即可展示树形结构
  • 一、什么是数据结构 1、数据结构的起源 1968年,美国的高纳德教授开设了一门基本算法的课程,开创了数据结构的先河。 数据结构是一门研究数据之间关系和操作的学科,而非是计算方法。 数据结构+算法=程序 沃思凭借这...
  • html中展示json数据结构

    千次阅读 2016-09-10 09:25:51
    附源码: html: Insert title here pre {  outline: 1px solid #ccc;  padding: 5px;  left: 50%;  position: absolute;  right: 0; } .content {  position: fixed;... lef
  • idea中项目包展示结构

    千次阅读 2020-09-15 15:35:54
    如下图,这中的,下下图中设置按钮打开,Flatten Packages,Compact Middle packages 都不选 如下图,这中的,下下图中设置按钮打开,只勾选Compact Middle packages 其他格式的自己玩组合就好
  • 此时如果直接将所有的部门从数据库中查询出来,让用户选择是可以的,但是显示出来的效果,不是很友好,这样会导致用户体验不好,因此在这里,我们可以一个小技巧来实现一个好的显示效果,那就是简单的树状结构,如图...
  • 上一篇文章讲解了链表的相关知识,并用代码实现了一个链表结构。那么本文将介绍一下另一种特殊的链表结构,叫做 双向链表。 顾名思义,普通的链表都是从 head 开始往后遍历...数据结构——双向链表一、什么是双向链表二
  • markdown 之项目目录文件结构展示

    万次阅读 2018-10-18 16:45:56
    一般来说,我们为项目写readme文档时,都会对整个目录的项目结构做个说明。 例如这样的: 我们可以用mddir来生成项目目录结构:mddir 使用命令 node mddir "../relative/path/" 例子 打开终端或命令...
  • 一般在构建模型的时候,如果能在训练之前就知道模型的参数量和结构图,就能避免一些低级错误。常用的函数有summary和plot_model,下面就一个简单的个例进行展示 另外,需要说明,在tensorflow 2.0版本中,tf.keras的...
  • 前端多级组织(部门)结构展示

    千次阅读 2018-05-24 17:10:08
    预期效果: 开发: 插件:jOrgChart 扩展:jOrgChart-tree 下载:jOrgChart 实操: html &lt;link rel="stylesheet" href="asset/jquery.jOrgChart.css"&......
  • java中的mvc和三层结构究竟是什么关系

    万次阅读 多人点赞 2016-12-12 17:21:52
    一件事,要知其然往往很简单,要知其所以然通常不是那么容易,就如最近重新巩固spring的过程中,就觉得还有许多...而mvc和三层结构究竟是什么关系,我曾在面试的过程中被人问过几次,也曾仔细的想过、查过这个问题,但
  • 从前几年开始,安防厂商就已经开始在强调视频结构化,经过算法的演进和技术的革新,视频结构化开始大规模地得到应用。那么,何为视频结构化?视频结构化是一种视频内容信息提取的技术,它对视频内容按照语义关系,...
  • 数据结构——优先级队列一、什么是优先级队列 一、什么是优先级队列 在了解了什么是队列以后,我们再来了解优先级队列,顾名思义,优先级队列就是在队列的基础上给每个元素加上了先后顺序,我们仍然拿排队买票的例子...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 590,018
精华内容 236,007
关键字:

展字的结构是什么结构