精华内容
下载资源
问答
  • 结构 非常得类似我们之前讲到过的树结构,但前者没有很多的...在数学的概念中,后者是前者的种,不过在数据结构中我们还是认为两者有所区别,尽管如此,我们在学习结构的时候仍可以稍微借鉴一下树结构的思想。

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

    展开全文
  • 数据结构的建立)——C语言
  • 数据结构 操作 研究 C语言实现 完整的代码 本人学习的时候写的 感觉很好 希望能给你们带来启发
  • 数据结构单链表的创建,插入,修改,查找以及删除。线性表操作
  • 无向邻接矩阵的创建代码实现完整代码如下程序结果 根据的定义,邻接矩阵的存储需要对顶点和边分别存储。而的邻接矩阵表示法是一个用一维数组存储顶点信息,用二维数组存储边(弧)的信息。实现这个算法首先要...

    无向图邻接矩阵的创建代码实现

    根据图的定义,邻接矩阵的存储需要对顶点和边分别存储。而图的邻接矩阵表示法是一个用一维数组存储顶点信息,用二维数组存储边(弧)的信息。实现这个算法首先要创建无向图,对图进行初始化操作,其次设置三个函数,分别为打印邻接矩阵,判断是否为对称矩阵和打印顶点的出度和入度。具体实现如下所示。

    完整代码如下

    #include<stdio.h>
    #include<malloc.h>
    #define maxnumber 6//顶点数目最大值
    typedef  struct
    {
    	char vexs[maxnumber];//顶点表
    	int  edges[maxnumber][maxnumber];//邻接矩阵,边表 
    	int n,e;//图的顶点数和弧数
    }MGraph;
    
    //创建无向图
    void CreateMGraph(MGraph *G)
    {
    	int i,j,k,max=0;
    	printf("请输入顶点数和边数(格式:顶点数,边数):\n");
    	scanf("%d,%d",&(G->n),&(G->e));
    
    	//图的初始化
    	for(i=0;i<G->n;i++)
    	{
    		printf("请输入第%d个顶点的信息:",i+1);
    		scanf("\n%c",&(G->vexs[i]));
    	}
    	printf("\n");
    	for(i=0;i<G->n;i++)
    	{
    		for(j=0;j<G->n;j++)
    			G->edges[i][j]=0;
    	}
    	printf("请输入每条边对应的两个顶点的序号(格式为:i,j):\n");
    	printf("\n");
    
    	//顶点信息存入顶点表
    	for(k=0;k<G->e;k++)
    	{
    		printf("请输入第%d个顶点和边的信息:",k+1);
    		scanf("%d,%d",&i,&j);
    		G->edges[i][j]=1;
    	}
    }
    
    //打印邻接矩阵
    void print_Matrix(MGraph G)
    {
    	int i,j;
    	printf("\n输出的邻接矩阵为:\n");
    	printf("\n");
    	for(i=0;i<G.n;i++)      //输出对应的领接矩阵 
    	{
    		for(j=0;j<G.n;j++)
    		{
    			printf("%d   ",G.edges[i][j]); 
    			if(j==(G.n-1)) 
    				printf("\n");    //输出结束 
    		}
    	}
    }
    
    //判断是否为对称矩阵
    void check_Matrix(MGraph G)
    {
    	int i,j,a;
    	for(i=0;i<G.n;i++)    //用于判断是否为对称矩阵 
    		for(j=0;j<G.n;j++)
    		{
    			if(G.edges[i][j]==G.edges[j][i])
    				a=1;
    			else
    			{
    				a=0;
    				break;
    			}
    		}   
    	if(a==1)
    		printf("矩阵是为对称矩阵\n");
    	else
    		printf("矩阵不是为对称矩阵\n");  
    }
    
    //输出顶点的出入度
    void output_Matrix(MGraph G)
    {
    	int i,j,cnt,max1,max2,max=0;
    	for(i=0,cnt=0;i<G.n;i++)    //用于输出顶点的出度
    	{
    		for(j=0;j<G.n;j++)
    		{
    			if(G.edges[i][j]==1)
    				cnt++; 
    			if(j==(G.n-1))
    				printf("%8d的出度为%d\n",i,cnt);
    			if(max<cnt)
    			{
    				max=cnt;
    				max1=i;
    			}
    		}
    	}
    	printf("%3d的出度最大\n",max1);
    	for(j=0,cnt=0,max=0;j<G.n;j++)    //用于输出顶点的入度
    	{
    		for(i=0;i<G.n;i++)
    		{
    			if(G.edges[i][j]==1)
    				cnt++; 
    			if(i==(G.n-1))
    				printf("%8d的入度为%d\n",j,cnt);
    			if(max<cnt)
    			{
    				max=cnt;
    				max2=i;
    			}
    		}
    		
    
    	}printf("%d的入度最大\n",max2);
    }
    void main() 
    {
    	MGraph G;
    	CreateMGraph(&G);//创建无向图
    	print_Matrix(G);//打印邻接矩阵
    	check_Matrix(G);//判断是否为对称矩阵
    	output_Matrix(G);//输出顶点的出入度
    }
    

    程序结果

    无向图的邻接矩阵创建

    展开全文
  • 数据结构创建

    万次阅读 多人点赞 2018-01-21 14:24:13
    (Graph):是由顶点的又穷非空集合和定点之间的边集组成,通常表示为G(V,E),其中G表示一个图,V是其顶点集合,E是其边集合。 有向(Directed graphs): 任意两个点之间的边都是有向边。 入度(InDegree):以顶点为...

    1.图的定义

    图(Graph):是由顶点的又穷非空集合和定点之间的边集组成,通常表示为G(V,E),其中G表示一个图,V是其顶点集合,E是其边集合。

    有向图(Directed graphs): 任意两个点之间的边都是有向边。

    入度(InDegree):以顶点为v为头的弧的数目称为入度。

    出度(OutDegree):以顶点v为尾的弧的数目成为出度。


    2.图的存储结构

    常见的存储结构有五种:

    • 邻接矩阵
    • 邻接表
    • 十字链表
    • 邻接多重表
    • 边集数组

    邻接矩阵:图的定义G(V,E),顶点可以用一维数组来存储type vex[n],边可以理解为线,当然就可以用二维数组
    type arc[n][n]进行存储。对于无向表该矩阵一定是对称矩阵,如果顶点i,j之间存在边那么arc[i][j],arc[j][i]=1否则arc[i][j]=0
    实例图

    存在的边:V0—-V1,V1—-V2 ,V2—V3 ,V3—V0即:

    arc[0][1]=arc[1][0]=1;
    arc[1][2]=arc[2][1]=1;
    arc[2][3]=arc[3][2]=1;
    arc[3][0]=arc[0][3]=1;

    其矩阵应该为:

    这里写图片描述

    某个顶点i所在行或者所在列元素之和即其度。
    对于有向表,矩阵不再是对称的,可以定义列顶点作为起点,行作为终点。那么顶点i所在行的元素和即为出度,列元素和即为入度。
    这里写图片描述
    由图可知:
    arc[0][3]=1;
    arc[1][0]=1;
    arc[1][2]=1;
    arc[2][0]=1;
    arc[2][1]=1;
    其矩阵为:
    这里写图片描述
    这种存储结构优缺点都十分明显,优点在于结构简单,能分清楚看出顶点的出度和入度,简单判断两个顶点间是否存在边。
    但是创建是遍历数组复杂都n^2,动态扩展困难,很多的存储空间的浪费。


    邻接表
    基于邻接矩阵,顶点依然用一维数据存放,但不仅仅存放顶点数据,还存放一个存储由以该定点为弧头邻接点的一维链表。
    这里写图片描述
    这种数据结构下,图就由一个链表数组构成。链表数据结构为:
    这里写图片描述
    在例子图中
    这里写图片描述
    依然可以轻松看出每一个顶点的出度或者入度(如果链表存放的是以顶点Vi为弧头的邻接点则是出度,为弧尾则是入度)。在有向表的情况下也是一样。只关注一个方向进行记录就好。
    虽然解决了邻接矩阵难以动态扩展和空间浪费的问题,但是依然存在一个问题,不能同时反应顶点的出度和入度,链表和数组相比,链表始终需要进行遍历(当然有算法可以减少查找次数),导致效率上始终比不上数组毕,竟数组只是一串连续的存储空间,很轻松就可以获取到目标值。

    边集数组
    这个办法思路更简单,用一个一维数组(或者链表)来存放所有边的信息,其结构是:
    begin end weight(权,如果有用到的话)
    这里写图片描述
    这种方法会使得出度入度及顶点信息都不是很好获得所以不常用。

    十字链表和多重链接表
    克服了邻接表不能同时显示入度和出度的问题,实现比前几个都复杂所以留到后面再写,不然这篇就太长了= =b。



    3.图的建立

    是时候敲敲代码了,这里的建立方法使用邻接表的方式,本来我想用Python来做图这种数据类型,但是数据结构本来的目的就是接近底层,所以这里还是使用C/C++来实现尽管要麻烦一些 = =。

    class Graph
    {
    public:
        typedef struct item
        {
            int index;
            int power;
            item*next=NULL;
        }NodeList,*Node;
        int num;
        Graph();
        ~Graph();
    private:
        NodeList vexs[20];//最多支持20个顶点
    };
    Graph::Graph()
    {
        int temp=0;
        int counts = 0;
        cout << "输入顶点个数:" << endl;
        cin >> num;
        for (int i = 1; i < num + 1; i++)
        {
            Node ptr = &vexs[i-1];
            cout << "输入第"<<i<<"个顶点信息" << endl;
            counts = 0;
            while (1)
            {
                cout << "输入链接下标" << endl;
                cin >> temp;
                if (temp == -1)
                {
                    ptr->next = NULL;
                    cout << "第" << i << "个节点录入完成" << endl;
                    break;
                }
                else
                {
                    if (counts > 0)
                    {
                        ptr->next = (Node)malloc(sizeof(NodeList));
                        ptr = ptr->next;
                    }
                    ptr->index = temp;
                    cout << "输入该边的权" << endl;
                    cin >> temp;
                    ptr->power = temp;
                    counts++;
                }
            }
        }
    }
    
    Graph::~Graph()
    {
    
    }

    这个版本很早以前写的,但还是可以用。
    这里又存在了一个数组,又可以进行抉择,追求速度可以就是用数组,想更高效的利用存储空间就可以利用链表。即顶点链表中每一个节点都包含着一个边链表,实现方法如下:
    首先因为是两个链表,直接整逻辑会显得很复杂,所以这里将它拆分为两个类,各自实现添加操作。

    /*******************边集链表*********************/
    class Node//边信息
    {
    public:
        char date;
        int wight;//权 暂未使用
        Node*next;
    };
    
    class LinkList
    {
    public:
        Node * head;//头指针
        Node * tail;//尾部指针
        int lenth=0;//链表长度
    
        LinkList(char *s);//用一个char数组初始化链表
        Node* add_one(char s);//返回一个当前指针
        void display();
        bool del(int index);
    };
    LinkList::LinkList(char*s)
    {
        if (s == NULL)
        {
            cout << "create a empty LinkList!" << endl;
            head = NULL;
            tail = NULL;
        }
        else
        {
            head = (Node*)malloc(sizeof(Node));
            Node *ptr = head;
            while (*s!='\0')
            {
                lenth++;
                ptr->date = *s++;
                ptr->next = (Node*)malloc(sizeof(Node));
                ptr = ptr->next;
            }
            ptr->date = '#';
            ptr->next = NULL;
            tail = ptr;
        }
    }
    
    Node* LinkList::add_one(char s)
    {
        Node *ptr;
        Node*curr;
        if (lenth == 0)//链表未曾进行过添加
        {
            head = (Node*)malloc(sizeof(Node));
            ptr = head;
            ptr->date = s;
            ptr->next= (Node*)malloc(sizeof(Node));
            ptr = ptr->next;
            ptr->date = '#';
            ptr->next = NULL;
            tail = ptr;
            lenth++;
            return head;
        }
        else
        {
            ptr = tail;
            ptr->date = s;
            curr = ptr;
            ptr->next = (Node*)malloc(sizeof(Node));
            ptr = ptr->next;
            ptr->date = '#';
            ptr->next = NULL;
            tail = ptr;
            lenth++;
            return curr;
        }
    }
    
    bool LinkList::del(int index)
    {
        if (index > lenth || index < 0)return false;
        Node*ptr=head;
        if (index == 0){
            head = head->next;
            free(ptr);
        }
        else {
            for (int i = 0; i < index - 1; i++)
            {
                ptr = ptr->next;
            }
            Node*temp = ptr->next;
            ptr->next = ptr->next->next;
            free(temp);
        }
        lenth--;
        return true;
    }
    
    void LinkList::display()
    {
        Node*ptr = head;
        for (int i = 0; i < lenth; i++)
        {
            cout << "LinkList[" << i << "]:" << ptr->date<<"  ";
            ptr = ptr->next;
        }
        cout << endl;
    }

    这个链表就用于存放顶点集,其构造方法和display方法是用于测试该表链是否有问题,构造图主要使用的是add_one()方法
    自动增加一个节点。

    /****************顶点集链表******************/
    class vex//顶点信息
    {
    public:
        LinkList *current;
        vex *next;
        char date;
    };
    
    class VexLinkList
    {
    public:
        vex*head;
        vex*tail;
        int lenth = 0;
        VexLinkList(char *s);
        vex* add_one(char s);
    };
    
    VexLinkList::VexLinkList(char *s)//顶点集
    {
        if (s == NULL)
        {
            head = NULL;
            tail = NULL;
            cout << "create a empty VexLinkList!" << endl;
        }
        else
        {
            head = (vex*)malloc(sizeof(vex));
            vex*ptr = head;
            while (*s!='\0')
            {
                lenth++;
                ptr->date = *s++;
                ptr->next = (vex*)malloc(sizeof(vex));
                ptr = ptr->next;
            }
            ptr->date = '#';
            ptr->next = NULL;
            tail = ptr;
        }
    }
    vex* VexLinkList::add_one(char s)
    {
        vex*curr;
        if (lenth == 0)
        {
            head = (vex*)malloc(sizeof(vex));
            head->date = s;
            head->next = (vex*)malloc(sizeof(vex));
            tail = head->next;
            tail->date = '#';
            tail->next = NULL;
            lenth++;
            return head;
        }
        else
        {
            tail->date = s;
            curr = tail;
            tail->next = (vex*)malloc(sizeof(vex));
            tail = tail->next;
            tail->date = '#';
            tail->next = NULL;
            lenth++;
            return curr;
        }
    }

    其实链表结构就那样,所以这两个链表其实差不多只是节点类型上有区别;add_one()方法依然自动添加一个节点。


    图类型结构

    class Graph
    {
    public:
        VexLinkList *t;//顶点集
        int sum;//顶点总数
        Graph();
    };
    Graph::Graph()
    {
        char temp;
        t = (VexLinkList*)malloc(sizeof(VexLinkList));
        t->lenth = 0;
        while (1)
        {
            cout << "input the vex # means none" << endl;
            cin >> temp;
            fflush(stdin);
            if (temp == '#')break;
            vex*cur=t->add_one(temp);
            cout << "now input the date in the vex" << endl;
            cur->current = (LinkList*)malloc(sizeof(LinkList));
            cur->current->lenth = 0;
            while (1)
            {
                cin >> temp;
                if (temp == '#')break;
                cur->current->add_one(temp);
            }
        }
    }

    这里设定了一个默认的终止字符’#’碰到’#’字符就认为当前的顶点集链表或者边集链表输入完毕。
    数据结构图:

    这里写图片描述

    最后

    相对于树的建立,感觉上图的建立还算比较简单,只是相关的概念非常多,遍历(深度,广度)相较二叉树稍显复杂,这里立一个flag,深度遍历,广度遍历,十字链表和多重邻接表下周来写,本来以为写这些应该很快,结果发现。。。好慢啊= =。最后吐槽一下markdown编辑器,真是帮人学习HTML CSS。

    展开全文
  • 数据结构中有关线性表的代码实现,完成了线性表创建,插入,删除,查找等功能。
  • 栈结构是一种非常常见的数据结构,并且在很多场景下也被用到。其实栈结构跟数组结构很像,只是在数组的基础...数据结构——栈一、什么是栈二、栈结构的方法三、用代码实现一个栈结构(1)创建一个构造函数(2)实现push

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

    栈结构是一种非常常见的数据结构,并且在很多场景下也被用到。其实栈结构跟数组结构很像,只是在数组的基础上,对栈结构做了一些限制,本文我们将对其进行详细的介绍。
    在这里插入图片描述

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

    一、什么是栈

    上面是说了,相对于数组结构做了一些限制。在使用数组结构的时候,我们可以任意的取出数组内的任何元素,也可以随意在指定位置插入元素,而却对元素的获取插入做了一些限制。

    我们可以形象地把栈理解成一个没有盖子的茶杯,例如下图
    在这里插入图片描述
    杯口的位置叫做栈顶
    杯底的位置叫做栈底

    现在我们往被子里放入一个物体,这个操作叫做入栈,这也就相当于我们向栈内插入一个元素
    在这里插入图片描述
    我们再进行一次入栈操作,结果如下
    在这里插入图片描述
    此时,我们想要从杯子里拿出一个物体,可以很明显的看到,物体1物体2盖住了,所以我们只能先拿到 物体2,所以,我们就把 物体2 取出了,这样的操作成为出栈,结果如下
    在这里插入图片描述
    此时再进行一次出栈操作,就把 物体1 拿出来了,此时栈就为空了,结果如下:
    在这里插入图片描述

    看了上面的讲解,相信你们对栈结构有了很深刻的印象,所以这里我来总结一下:

    • 栈是一种受限的线性数据结构,它对元素的操作遵循的是先进后出,也就是向入栈的元素会比后入栈的元素晚一点取出来。

    二、栈结构的方法

    我们都知道像数组结构,都有一些操作元素的方法,例如在末尾插入元素 、在头部插入元素 、删除指定位置的元素等等,同样的,栈结构也是有它自己的操作元素的方法的,接下来我们就来介绍一下,栈结构常用的操作元素的方法有哪些吧。

    方法含义
    push()入栈操作
    pop()出栈操作
    getTopElement()返回栈顶的元素,但不会移除栈顶的元素
    isEmpty()查看栈是否为空
    size()返回栈内元素的个数
    toString()以字符串的形式展示栈内的所有元素

    三、用代码实现一个栈结构

    接下来,我们就用JavaScript封装实现一个基于数组的栈结构的类,因为是基于数组实现的栈,所以我们可以把数组的头部看作是栈底,把数组的尾部看作是栈顶

    (1)创建一个构造函数

    首先就是声明一个构造函数Stack,然后并在内部创建一个空数字,用于储存数据元素

    function Stack() {
    	//属性
        this.list = []
    }
    

    (2)实现push()方法

    push()方法就是进行入栈操作,所以我们需要向栈顶(数组的尾部)插入元素

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

    function Stack() {
    	//属性
    	this.list = []
    	
        //push()方法的实现
        Stack.prototype.push = function (e) {
            this.list.push(e)
        }
    }
    

    我们来使用一下该方法

    let stack = new Stack()
    stack.push(3)
    stack.push(9)
    stack.push(5)
    

    经过上面操作后,栈内的情况是这样的:
    在这里插入图片描述

    (3)实现pop()方法

    pop()方法就是进行出栈操作,所以我们需要取出栈顶的第一个元素(数组的尾部),并返回取出的元素

    接下来我们就来实现一下该方法

    function Stack() {
    	//属性
    	this.list = []
    	
        //pop()方法的实现
        Stack.prototype.pop = function (e) {
            return this.list.pop()
        }
    }
    

    我们来使用一下该方法

    let stack = new Stack()
    //先按 3 9 5 的顺序入栈,再进行出栈操作
    stack.push(3)
    stack.push(9)
    stack.push(5)
    
    stack.pop()        //返回 5
    

    此时栈内的情况是这样的,元素5被取出,此时栈顶第一个为元素9
    在这里插入图片描述

    (4)实现getTopElement()方法

    getTopElement()方法就相当于是查看一下栈顶的元素是什么(查看数组尾部的元素),而不会对栈内元素进行任何的入栈或出栈操作

    我们来实现一下该方法

    function Stack() {
    	//属性
    	this.list = []
    	
        //getTopElement()方法的实现
        Stack.prototype.getTopElement = function () {
            return this.list[this.list.length - 1]
        }
    }
    

    我们来使用一下该方法

    let stack = new Stack()
    //先按 3 9 5 的顺序入栈,再查看一下栈顶元素是什么
    stack.push(3)
    stack.push(9)
    stack.push(5)
    
    stack.getTopElement()     //返回 5
    

    (5)实现isEmpty()方法

    isEmpty()方法就是看看栈内是否有元素(查看数组是否为空),有的话就返回 false,没有就返回 true

    我们来实现一下该方法

    function Stack() {
    	//属性
    	this.list = []
    	
        //isEmpty()方法的实现
        Stack.prototype.isEmpty = function () {
            let size = this.list.length
            if(size === 0) {
                return true
            }
            else {
                return false
            }
        }
    }
    

    我们来使用一下该方法

    let stack = new Stack()
    
    stack.isEmpty()    // true,因为此时还没有插入元素
    
    stack.push(3)
    
    stack.isEmpty()   // false,将 3 入栈了,所以栈不会空,返回false
    

    (6)实现size()方法

    size()方法就是查看栈内有多少元素(查看数组的长度)并返回

    我们来实现一下该方法

    function Stack() {
    	//属性
    	this.list = []
    	
        //size()方法的实现
        Stack.prototype.size = function () {
            return this.list.length
        }
    }
    

    我们来使用一下该方法

    let stack = new Stack()
    
    stack.size()       // 0,因为还没进行过入栈操作
    
    stack.push(4)
    stack.push(7)
    
    stack.size()       //  2,因为栈内有两个元素,所以返回 2
    

    (7)实现toString()方法

    toString()方法就是将栈内的元素用字符串的方式展示出来(将数组转化成字符串)并返回

    我们来实现一下该方法

    function Stack() {
    	//属性
    	this.list = []
    	
        //toString()方法的实现
        Stack.prototype.toString = function () {
            let string = ''
            for(let i in this.list) {
                string += `${this.list[i]} `
            }
            return string
        }
    }
    

    我们来使用一下该方法

    let stack = new Stack()
    
    stack.push(3)
    stack.push(9)
    stack.push(5)
    
    stack.toString()        //   返回 3 9 5
    

    四、栈结构的实战应用

    现在需要通过栈结构实现一个函数,将输入的十进制转化成二进制

    我们都知道,十进制转二进制是将一个数每次都除以2,一直到无法再除以2以后,倒着将每次除以2后获得的余数连接起来,就是正确的二进制数,如下图
    在这里插入图片描述
    所以,我们可以看到,最先获得的余数是最后才被取走的,这是一个很典型的栈结构的例子。每次除得的余数,就对其进行入栈操作,最后再进行多次出栈操作就可以实现十进制转二进制的功能了。

    因此我们来封装一下这样一个函数

    function d2b(number) {
        let stack = new Stack()
    
        while (number > 0) {
    
            stack.push(number % 2)
    
            number = Math.floor(number / 2)
        }
    
        let string = ''
        while (!stack.isEmpty()) {
            string += stack.pop()
        }
    }
    

    我们来使用一下这个函数,看看是否正确

    d2b(100)           //返回 1100100
    

    好了,这个例子的功能函数封装完成了

    五、总结

    栈结构的讲解就到这里了,希望大家对栈结构有了更深一层的理解。下一篇文章我将讲解一下队列

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

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

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

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

    展开全文
  • 数据结构之二叉树的代码实现 C语言版

    千次阅读 多人点赞 2019-08-20 11:06:18
    二叉树的创建,三种遍历,求叶子结点树,深度,结点数
  • 数据结构 创建结构体学生表 c语言

    千次阅读 2019-01-30 21:35:12
    以单链表形式创建一个学生表,并能实现相关的创建、销毁、清空、查找、插入和删除等算法。 需要定义学生表的结构体 linklist.h代码: typedef struct link_node//定义结构体,包含学生学号 语文 数学 英语...
  • 目录 基础 c/c++ 代码优化及常见错误 ...除树和外的数据结构可以使用STL: C++ STL的使用 数据结构 线性表 顺序表 循环左移(2010联考真题) 单链表 单链表相邻结点逆置(2019北邮考研真...
  • 队列结构也是平时非常常见的一种受限的线性数据结构。它跟栈结构一样都是受限的数据结构,区别就是...数据结构——队列一、什么是队列二、队列结构的方法三、用代码实现一个队列结构(1)创建一个构造函数(2)实现enq
  • Mysql创建结构代码 CREATE TABLE `user` ( `id` int(11) NOT NULL auto_increment, `name` varchar(255) NOT NULL, `pwd` varchar(255) NOT NULL, `sex` varchar(255) NOT NULL, `home` varchar(255) NOT ...
  • 数据结构-顺序表基本操作的实现(含全部代码

    万次阅读 多人点赞 2018-09-13 22:14:57
    今天起开始编写数据结构中的各种数据结构及其算法的实现。 主要依据严蔚敏版数据结构教材以及王道数据结构考研辅导书。 今天是线性表中的顺序表的实现,主要实现函数如下,读者有需要可以评论,我可以适当加几。...
  • 数据结构创建(邻接表法创建

    千次阅读 多人点赞 2019-04-22 20:57:38
    在邻接表中,对图的每个顶点建立一个单链表,第I个单链表的结点依附于顶点V的边。 邻接表的存储结构 个人感觉邻接表的难点在于创建三种结构体,并将他们三个联系起来,过程中多了很多名词,需要大家细心去领会,...
  • 用C语言来创建一个顺序表(数据结构部分)

    万次阅读 多人点赞 2019-06-17 17:30:13
    顺序表的创建需要用到结构体,构造一个结构体来存储数据,顺序表申请的内存是连续的。创建顺序表的思路按照数据的“增删改查来进行编写”下列是顺序表的创建代码 创建头文件: sqlist.h #ifndef SQLIST_H #...
  • 数据结构(c语言版)代码

    万次阅读 多人点赞 2019-01-07 13:42:00
    章作为绪论,主要介绍了数据结构与算法中的一些基本概念和术语。对于这些概念术语,我个人不推崇死记硬背,记住了当然好,记不住也没关系,但是一定要做到完全理解。就算嘴上说不出来,心里也一定要明白这...
  • /* *顺序储存无向邻接矩阵...*创建一个无向 *输出无向的邻接矩阵 */ #include<stdio.h> #include<string.h> #include<stdlib.h> #define MAXVERTEX 100//顶点数 #define ERROR 0 #defi...
  • 数据结构创建无向

    千次阅读 2019-01-25 20:52:43
  • MySQL创建数据库和创建数据

    万次阅读 多人点赞 2019-10-20 23:44:40
    MySQL 创建数据库和创建数据表 MySQL 是最常用的数据库,在...数据库在操作时,需要使用专门的数据库操作规则和语法,这语法就是SQL(Structured Query Language) 结构化查询语言。 SQL 的主要功能是和数据库...
  • 代码比较简单,没有完全按照严蔚敏版《数据结构(C语言版)》上39页到43页上的要求,只是实现了简单功能,且此代码输入多项式时只能按升幂的顺序输入(因为没有写多项式排序的函数) 个人感觉此代码短小精悍,且易...
  • 数据结构-单链表基本操作-C语言代码

    万次阅读 多人点赞 2020-01-22 19:51:58
    本篇只有c语言代码,具体思路讲解请看这篇博客:数据结构-线性结构-单链表 1.头插法建立单链表 #include<stdio.h> #include<stdlib.h> //单链表的结构定义 typedef struct LNode { int data...
  • 数据结构_单链表的创建

    千次阅读 2018-04-27 20:15:05
    printf("输入要创建的元素数:"); scanf("%d", &n); ElementType val; for (int i = 0; i ; i++) { printf("请输入第 %d 元素:", i + 1); scanf("%d", &val); s = (List)malloc(sizeof(struct Node...
  • 数据结构栈的创建(c语言)

    千次阅读 2019-06-18 12:10:05
    栈是种线性数据结构,采用先进后出的方式管理数据其中段固定,称之为栈底,另一端随着数据进出而随时改变位置,叫做栈顶,用程序实现栈一定要记录栈顶的位置,往栈放入数据操作称之为入栈(压栈),从栈中取出数据...
  • 数据结构-快速排序(含全部代码

    万次阅读 2021-03-15 17:09:19
    代码 全部代码 截图 算法可视化 函数分析 QuickSort(SqList &L,int low,high) 参数:顺序表L,待排最小下标,待排最大下标 功能:排序(默认升序)空间复杂度:O(1) 时间复杂度:O(nlog2n)-O(n) 稳定性:不...
  • 这是我第一次自己写出一个完整的数据结构代码,放在这里记录一下。同时也在梳理一遍代码的结构。 代码实现的是链式存储建立多项式并输出。 #include <iostream> using namespace std; // 定义多项式的节点 ...
  • 数据结构采用邻接表表示法创建无向

    万次阅读 多人点赞 2018-11-19 22:10:54
    数据结构&lt;采用邻接表表示法创建无向&gt;&lt; h1/&gt;” 算法步骤: 1.输入总顶点数和总边数 2.依次输入点的信息存入顶点表中,是每表头结点的指针域初始化为NULL 3.创建邻接表。依次输入每条...
  • C语言创建一个链表的代码

    千次阅读 2019-01-23 12:28:08
    把开发过程常用的一些代码做个收藏,下边代码是关于C语言创建一个链表的代码。 #include "stdlib.h" #include "stdio.h" struct list { int data; }; typedef struct list node; void main() { ...
  • 数据结构-冒泡排序(含全部代码

    万次阅读 2021-03-15 16:46:52
    使用一个标记,有交换时标记,若一趟下来没有需要交换的,则停止。 void BubbleSort(SqList &L) 参数:顺序表L,时间复杂度O(n^2),空间复杂度O(1),稳定性:稳定 代码 //冒泡排序 升序排序 void BubbleSort...
  • 是不同于树的另种非线性数据结构。在树结构中,数据元素之间存在着种...即中的每数据元素可以和中任意别的数据元素相关,所以种比树更复杂的数据结构。 树结构可以看做是种特例。   ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,374,045
精华内容 549,618
关键字:

数据结构创建一个图代码

数据结构 订阅