目录
一、堆
1、概念
是计算机科学中一类特殊数据结构的统称;
堆通常是一个可以被看做一棵树的数组对象。
2、堆总是满足下列性质
堆中某个节点的值,总是不大于或不小于其父节点的值;
堆总是一棵完全二叉树(完全二叉树压树时,每一层的左右节点都是有数的,不应该有空的。)。
3、考法1:大/小顶堆
解题方式:按照“层次遍历”的方式,将选项压成一棵二叉树,进而得到结果。
层级遍历:从上往下,同一层有多个节点则从左往右。
注意:因为“堆”是一棵完全二叉树,所以压树时,每一层的左右节点都是有数的,不应该有空的。
二、图
1、概念
由集合V和E构成的二元组,记作G=(V,E)。
V:代表点;为了与树形结构区别,在图结构中常将结点称为顶点;
E:代表边,分为有向边、无向边;
所以图可以简单理解为由点和边构成的集合,有向图每条边都有方向,无向图每条边都没有方向。
2、度
与顶点v相关的边的条数为顶点的度。
3、入度
在有向图中,指向顶点v的边的条数称为顶点v的入度。
4、出度
由顶点v发出的边的条数称为顶点v的出度。
5、有向完全图和无向完全图
在有向图中有n个顶点,则最多有n(n-1)条边(图中任意两点都有两条边相连),将具有n(n-1)条边的有向图称为有向完全图。
若无向图中有n个顶点,则最多有n(n-1)/2条边(任意两个顶点之间都有一条边),将这种无向图称为完全无向图。
三、图的存储结构:领接矩阵表示法
1、有向图的领接矩阵表示法
用n*n的矩阵存放图中的信息;n就是图中点的个数。
第一行存的是节点1与其他节点的关系情况;第一行第一个元素表示节点1与节点1的关系,第一行第二个元素表示节点1与节点2的关系......
第一个元素是0,因为节点1没有有向边指向节点1;第二个元素是1,因为节点1有一条边指向节点2;以此类推。
注意箭头是出度时,矩阵元素才是1;
2、无向图的领接矩阵表示法
用n*n的矩阵存放图中的信息;n就是图中点的个数。
第一行存的是节点1与其他节点的关系情况;第一行第一个元素表示节点1与节点1的关系,第一行第二个元素表示节点1与节点2的关系............
第一个元素是0,因为节点1与节点1之间没有边;第二个元素是1,因为节点1与节点2之间有一条边;以此类推。
不需要考虑箭头的方向,只要右边相连接就是1。