基本数据结构：链表，图，树
算法第三章
#链表
链表由优先的元素（或节点）序列组成，节点包含：信息和到下一个节点的指针。基本操作有插入和删除。对链表的访问加一些限制，就能得到另外两种数据结构：堆栈和队列。
##专有名词
表头、节点、前驱节点
##分类
- 单向链表：记录下一个节点的地址
- 循环链表：链表中最后一个元素记录了第一个元素的地址
- 双向链表：每一个节点也指向他的前驱节点
#堆栈和队列
堆栈是一种只允许在栈顶进行插入和删除运算的链表（也可以在数组中实现这些运算）
#图
图G=(V, E)有一个顶点集合V和一个边集合E组成。图既可以是有向的，也可以是无向的。如果G是无向的，那么E中每一条边都是一个无序的定点对；如果G是有向的，那么边为有序的顶点对。
无向图中顶点的度是和他邻接的顶点的个数；有向图中顶点的入度和出度分别是连接到该顶点的边和从该顶点连接到其他顶的的边的个数。
##专有名词
路径，路径是简单的（路径上所有顶点都不同）、回路，奇回路（奇数长度的回路）
无回路图
连通图：每一个顶点到其他顶点都是可达的，一个图的连通分支是图的最大连通子图
有向图中，如果子图的每一对顶点都相互可达，则这个子图称为强连通分支
完全图：一个图（无向/有向）的每一对顶点之间都恰有一条边
- 另
G=(V, E)是有n个顶点的完全无向图，那么|E| = n(n-1)/2 - 另
G=(V, E)是有n个顶点的完全有向图(名词对不对a...)，那么|E| = n(n-1)
二分图：如果无向图G=(V, E)中，V可以分为两个不相交的子集X和Y，是的E中每一天边的一端在X中，而另一端在Y中，则这个无向图称为二分图。
完全二分图：既是二分图，也是完全图。
##图的表示
布尔矩阵（邻接矩阵）：有边为1，无边为0
邻接矩阵的性质：
- 对无向图而言，邻接矩阵一定是对称的，主对角线一定为0；
- 在无向图中，任一顶点i的度为第i列的所有非零元素；在有向图中，顶点i的出度为第i行非零个数，入读为第i列非零个数
邻接表：而且节省空间
##平面图
如果图G=(V, E)可以嵌入平面而没有任何边相互穿越，这个图就使平面图
平面图定点数，边数和区域数之间的关系：定点数n，边数m，区域数r
n-m+r=2 和 m <= 3n - 6
#树
一个自由树是不包含回路的连通无向图。一个森林是顶点不相交的树的集合
根树：一颗带有特殊顶点r的树，顶点r为树的根
父节点，子节点，兄弟节点
叶子节点，内部顶点（除叶子节点外所有）
祖先，真祖先，后代，真后代
顶点v的深度是从根顶点到v的路径长度，根顶点深度为0，
##树的遍历
对一棵树的顶点进行系统的遍历和排序，其中最重要的三种为：前序遍历、中序遍历、后序遍历
##二叉树
满二叉树：二叉树中每个内部节点都正好有两个儿子
完全二叉树：是满二叉树，而且所有叶子节点有同样的深度
几乎完全二叉树：除了最右边位置上的一个或几个叶子可能缺少外，他是丰满的
##二叉树的一些定量特征
第j层顶点最多为：
2^j高度为
k的完全二叉树顶点数：2^(k+1) - 1高度为
k（根到也得边数），则有0-k层，供k+1层任何有n个顶点得二叉树，高度至少为
log(n)向下取整，最多为n-1有n个顶点得完全或几乎完全二叉树高度为
log(n)向下取整在完全二叉树中，叶子数等于内部节点数加1
通常，会设n0, n1, n2,分别表示度为0得节点（叶子），度为1得节点，度为2得节点
n = n0 + n1 + n2
n0 = n2+1
n1在完全二叉树中，只可能取值1或0
##二叉搜索树
非常重要得一种数据结构，搜索复杂度达到long(n)