数据结构概论
数据结构是计算机存储、组织数据的方式。常见的数据结构分类方式如下图：
常用的线性结构有：线性表，栈，队列，循环队列，数组。线性表中包括顺序表、链表等，其中，栈和队列只是属于逻辑上的概念，实际中不存在，仅仅是一种思想，一种理念；线性表则是在内存中数据的一种组织、存储的方式。
顺序表
顺序表将元素一个接一个的存入一组连续的存储单元中，在内存物理上是连续的。如下图：
顺序表存储密度较大，节省空间；但需要事先确定容量，在时间性能方面，读运算较快，时间复杂度为O(1)；查找运算为O(n/2)，和链表同样；插入运算和删除运算如果要操作中间一个元素，比如3，那么就需要把3后面的元素全部进行移动，因此时间复杂度相对链表要大一些，插入时间复杂度最好为O(0)或最坏为O(n)；删除时间复杂度为O([n-1]/2)；
链表
链表拥有很多结点，每个结点前半部分是数据域，后半部分是指针域，指针域指针指向下一个结点；链表可分为单链表、循环链表和双链表。
单链表：
从上图可以看出，单链表的上一个结点指针指向下一个结点，最后一个结点的指针域为null。
结点的删除：
删除一个结点，如删除上图中q结点，只需将p结点中的指针域指向a3，然后将a2释放掉（free）即可。
结点的插入：
插入一个结点，如插入上图中s结点，首先将s的指针域指向a2（也就是把s的next赋值为p的next），然后将p结点的指针域指向x即可（p的next指向x）。
循环链表
循环链表与单链表唯一不同之处是，循环链表的最后一个结点指针不为空，而是指向头结点。结点的插入和删除和单链表非常相似，就不再示范了。
双链表
双链表拥有一前一后两个指针域，从两个不同的方向把链表连接起来，如此一来，从两个不同的方向形成了两条链，因此成为双链表。因此，双链表的灵活度要大于单链表。
结点的删除：
双链表的操作比单链表要稍显复杂（按照单链表思路来做其实也不难），如上图，要删除p节点，首先需要将a1的后驱指向a3，然后将a3的前驱指向a1，最后将p节点释放掉即可。
结点的插入:
如上图，插入q结点，首先要按照方向，将步骤拆分，首先将q节点的前驱指向p结点后驱，紧接着将x后驱指向a2；然后按照顺序完成图中所示的3、4步即可。（经@llhhyy1989 @voteforvip @wanghuan203 三位童鞋的指正，发现此处有误，正确插入方法可查看评论，为保留错误原文不做改动！不懂具体插入过程可移步：http://hiphotos.baidu.com/zhidao/pic/item/b58f8c54fee5c3663a2935e0.jpg）
从空间性能来看，链表的存储密度要差一些，但在容量分配上更灵活一些。从时间性能来看，查找运算与顺序存储相同，插入运算和删除运算的时间复杂度为O(1)，要更优于顺序存储，但读运算则弱一些，为O([n+1]/2)，最好为1，最坏为n。
栈
上面提到栈属于一个逻辑概念，栈的实现可以用顺序也可以用链式。它遵循先进后出原则，如下图：
Java中测试代码如下：
package com.snail.test;
import java.util.Stack;
public class TestStack {
public static void main(String[] args) {
Stack<String> stack = new Stack<String>();
stack.push("NO1");
stack.push("NO2");
stack.push("NO3");
System.out.println("初始数量：" + stack.size());
while(!stack.isEmpty()){
System.out.println(stack.pop());
}
System.out.println("取完后的数量：" + stack.size());
}
}
输出结果顺序为：初始数量：3，NO3，NO2，NO1，取完后的数量：0。
队列
队列遵循先进先出的原则，如下图：
Java中测试代码如下：
package com.snail.test;
/**
*
* @author Zang XT
*/
import java.util.Queue;
import java.util.LinkedList;
public class TestQueue {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<String>();
queue.offer("NO1");
queue.offer("NO2");
queue.offer("NO3");
System.out.println("初始数量" + queue.size());
String str;
while((str=queue.poll())!=null){
System.out.println(str);
}
System.out.println("取出后数量" + queue.size());
}
}
运行结果顺序为：初始数量3，NO1，NO2，NO3，取出后数量0。
队列还有一种形式为循环队列，如下图：
循环队列有两个指针，头指针head和尾指针tail，尾指针一般指向的不是队尾元素实际地址，而是指向实际地址的下一个空地址，因此，循环队列一般牺牲最后一个空间，用来计算该队列是否满了，判断方式是tail+1 = head，既该队列已满。
树
一、树(Tree）定义
是n（n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中：
（1）有且仅有一个特定的称为根（root）的结点。
（2）当n>1时，其余结点可分为m（m>0)个互不相交的有限集T1,T2,....,Tm, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree)，如图1所示：
树的定义之中还用到了树的概念，即递归定义。如图2中的子树T1和T2就是根结点A的子树。当然D,G,H,I组成的的树又是B结点的子树，E,J 组成的树是C结点的子树。
对于树的定义还需要注意两点：
- n>0时根结点是唯一的，不可能存在多个根结点。
- m>0时，子树的个数没有限制，但它们一定是互不相交的。如图3中的两个结构就不符合树的定义，因为它们都有相交的子树。
二、树的结点
树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度（Degree）。度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点或分支结点，除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。如图4，因为这棵树结点的度的最大值是结点D的度3，所以树的度也为3
结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲（Parent），同一个双亲的孩子之间互称为兄弟（Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。所以对于H来说，D，B，A都是它的祖先。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。B的子孙有D,G,H,I，如图5所示。
三、结点的层次（Level)
从根开始定义起，根为第一层，根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。显然在图6中D,E,F都是堂兄弟，而
G,H,I 与 J也是堂兄弟。树中结点的 最大层次称为树的深度（Depth)或高度，当前树的深度为4（注：也有一些书是定义为branches的个数，此时认为
深度为3）。
若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(OrderedTree)；否则称为无序树(UnorderedTree)。注意：若不特别指明，一般讨论的树都是有序树。
森林(Forest)是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。对于图1的树而言，图2的两棵子树其实就可以理解为森林。树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。
对比线性表与树的结构，它们有很大不同，如图7所示。
图
图概述
图(Graph)是一种比线性结构和树形结构都要复杂的数据结构。简单讲，图是由表示数据元素的的集合V和表示数据之间关系的集合E组成。其中，数据元素常称作顶点(vertex)，数据之间的关系常称作边(edge)。故图可记为G=<V,E>，其中V是顶点的有穷非空集合，E是边的集合。在图中顶点的前驱和后继是不设限制的，因此图描述的是一种网状关系。
无向图
若边是无序的或者说是无向的，则称此图是无向图。若无向图中有边(vi,vj)(无向图中边用圆括号表示)，则显然(vj,vi)和(vi,vj)是同一条边。
有向图
若边是有序的或者说是有向的，则称此图是有向图。若有向图中有边<vi,vj>(有向图中边用尖括号表示)，则显然<vj,vi>和<vi,vj>不是同一条边。有向图中的边也称为弧(arc)，对于弧<vi,vj>，vi是弧尾(边的起点)，vj是弧头(边的终点)。
示例图
无向图 G1=<V1,E1> V1={v0,v1,v2,v3,v4} E1={(v0,v1),(v0,v2),(v1,v3),(v2,v3),(v2,v4),(v3,v4)}
有向图 G2=<V2,E2> V2={v0,v1,v2,v3} E2={<v0,v1>,<v0,v2>,<v2,v0>,<v2,v3>,<v3,v0>}
图的存储
所谓的图的存储，主要是想从存储结构中表达各顶点之间的联系，也就是表现图中的边。因为顶点总是很好存储的，如最常见的一维数组存储边：
顶点
| v0 | v1 | v2 | v3 | v4 |
或者是
| A | B | C | D | E
邻接矩阵(adjacency matrix)和邻接表(adjacency list)是图的两种常见存储方式。
如上，无向图G1，对于顶点Vi和顶点Vj，若有边，则(Vi,Vj)=1，否则(Vi,Vj)=0。显然(Vi,Vi)=0，此时的邻接矩阵如下：
V0 V1 V2 V3 V4
V0 0 1 1 0 0
V1 1 0 0 1 0
V2 1 0 0 1 1
V3 0 1 1 0 1
V4 0 0 1 1 0
显然，由于是无向图，该矩阵是对称的。邻接矩阵所需的存储空间的大小与边数无关，而与顶点数有关。它所需的空间复杂度是O(n^2)，n是顶点数。
同样的，若是使用邻接表来存储无向图G1，邻接表如下：
邻接表实质就是链式存储。
对于有权图，在邻接矩阵中只需把1改为为相应的权值即可，在邻接表中顶点结构体则需添加成员表示权值。
常用概念
- 顶点的度(degree)：与顶点关联的边的数目，记为D(v)。特别的，在有向图中，把顶点v作为终点的弧的数目是入度(in degree)，记为ID(v)；把顶点v作为起点的弧的数目是出度(out degree)，记为OD(v)。显然，D(v)=ID(v)+OD(v)。
- 顶点v1和顶点v2若是有边相连的，则称它们是相邻的(adjacent)。
- 用n表示顶点数，e表示边数。则无向图中e是0,n(n-2)/2；有向图中e是[0,n(n-1)]。
- 边数较少的图称为稀疏图(sparse graph)，边数较多则称为稠密图(dense graph)。
- 完全图：任意两个顶点之间都有边相关联的是完全图。完全图中边数达到最大。细分为无向完全图和有向完全图。
- 有时边是带有权值的，这个权值可以表示从一个顶点到另一个顶点的距离、代价、耗费等。这样的图也称为带权图。
- 子图：设G=<V,E>是一个图，V1是V的子集，E1是E的子集，且E1中的边只与V1中的顶点有关，则称G1=<V1,E1>是G的的子图(subgraph)。
- 路径：在无向图中顶点序列：vi,vj,…,vk，且相邻两顶点之间是有边的，则这个序列构成一条路径。在有向图中，构成路径的不仅是要有边，而且边的方向正确：只能是起点到终点。
- 简单路径：路径中不存在重复顶点，则是简单路径(simple path)。
环：在一条路径中，只有第一个顶点和最后一个顶点相同，这条路径就是环(cycle)或回路。
路径长度：路径上边的数目。
- 无环图：没有环的图(acyclic graph)。在有向图中，那就是有向无环图。
- 在无向图中，若顶点vi和vj是有路径的，则称vi和vj是连通的(connected)。若图中任意两个顶点都是连通的，则称该图是连通图。
- 连通分量：无向图中的极大连通子图。(所谓的极大是指再加入任意一个顶点，则不连通)
在有向图中，任意两个顶点之间都有一条有向的路径，则称该有向图是强连通图。
- 强连通分量：有向强连通的极大子图称为有向图的强连通分量或强连通分支。
概论看不懂没关系.后面会用更简单的方法介绍.听起来吓人那就对了
数据结构概论
数据结构是计算机存储、组织数据的方式。常见的数据结构分类方式如下图：
常用的线性结构有：线性表，栈，队列，循环队列，数组。线性表中包括顺序表、链表等，其中，栈和队列只是属于逻辑上的概念，实际中不存在，仅仅是一种思想，一种理念；线性表则是在内存中数据的一种组织、存储的方式。
顺序表
顺序表将元素一个接一个的存入一组连续的存储单元中，在内存物理上是连续的。如下图：
顺序表存储密度较大，节省空间；但需要事先确定容量，在时间性能方面，读运算较快，时间复杂度为O(1)；查找运算为O(n/2)，和链表同样；插入运算和删除运算如果要操作中间一个元素，比如3，那么就需要把3后面的元素全部进行移动，因此时间复杂度相对链表要大一些，插入时间复杂度最好为O(0)或最坏为O(n)；删除时间复杂度为O([n-1]/2)；
链表
链表拥有很多结点，每个结点前半部分是数据域，后半部分是指针域，指针域指针指向下一个结点；链表可分为单链表、循环链表和双链表。
单链表：
从上图可以看出，单链表的上一个结点指针指向下一个结点，最后一个结点的指针域为null。
结点的删除：
删除一个结点，如删除上图中q结点，只需将p结点中的指针域指向a3，然后将a2释放掉（free）即可。
结点的插入：
插入一个结点，如插入上图中s结点，首先将s的指针域指向a2（也就是把s的next赋值为p的next），然后将p结点的指针域指向x即可（p的next指向x）。
循环链表
循环链表与单链表唯一不同之处是，循环链表的最后一个结点指针不为空，而是指向头结点。结点的插入和删除和单链表非常相似，就不再示范了。
双链表
双链表拥有一前一后两个指针域，从两个不同的方向把链表连接起来，如此一来，从两个不同的方向形成了两条链，因此成为双链表。因此，双链表的灵活度要大于单链表。
结点的删除：
双链表的操作比单链表要稍显复杂（按照单链表思路来做其实也不难），如上图，要删除p节点，首先需要将a1的后驱指向a3，然后将a3的前驱指向a1，最后将p节点释放掉即可。
结点的插入:
如上图，插入q结点，首先要按照方向，将步骤拆分，首先将q节点的前驱指向p结点后驱，紧接着将x后驱指向a2；然后按照顺序完成图中所示的3、4步即可。（经@llhhyy1989 @voteforvip @wanghuan203 三位童鞋的指正，发现此处有误，正确插入方法可查看评论，为保留错误原文不做改动！不懂具体插入过程可移步：http://hiphotos.baidu.com/zhidao/pic/item/b58f8c54fee5c3663a2935e0.jpg）
从空间性能来看，链表的存储密度要差一些，但在容量分配上更灵活一些。从时间性能来看，查找运算与顺序存储相同，插入运算和删除运算的时间复杂度为O(1)，要更优于顺序存储，但读运算则弱一些，为O([n+1]/2)，最好为1，最坏为n。
栈
上面提到栈属于一个逻辑概念，栈的实现可以用顺序也可以用链式。它遵循先进后出原则，如下图：
Java中测试代码如下：
输出结果顺序为：初始数量：3，NO3，NO2，NO1，取完后的数量：0。
队列
队列遵循先进先出的原则，如下图：
Java中测试代码如下：
运行结果顺序为：初始数量3，NO1，NO2，NO3，取出后数量0。
队列还有一种形式为循环队列，如下图：
循环队列有两个指针，头指针head和尾指针tail，尾指针一般指向的不是队尾元素实际地址，而是指向实际地址的下一个空地址，因此，循环队列一般牺牲最后一个空间，用来计算该队列是否满了，判断方式是tail+1 = head，既该队列已满。
树
一、树(Tree）定义
是n（n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中：
（1）有且仅有一个特定的称为根（root）的结点。
（2）当n>1时，其余结点可分为m（m>0)个互不相交的有限集T1,T2,....,Tm, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree)，如图1所示：
树的定义之中还用到了树的概念，即递归定义。如图2中的子树T1和T2就是根结点A的子树。当然D,G,H,I组成的的树又是B结点的子树，E,J 组成的树是C结点的子树。
对于树的定义还需要注意两点：
二、树的结点
树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度（Degree）。度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点或分支结点，除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。如图4，因为这棵树结点的度的最大值是结点D的度3，所以树的度也为3
结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲（Parent），同一个双亲的孩子之间互称为兄弟（Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。所以对于H来说，D，B，A都是它的祖先。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。B的子孙有D,G,H,I，如图5所示。
三、结点的层次（Level)
从根开始定义起，根为第一层，根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。显然在图6中D,E,F都是堂兄弟，而
G,H,I 与 J也是堂兄弟。树中结点的 最大层次称为树的深度（Depth)或高度，当前树的深度为4（注：也有一些书是定义为branches的个数，此时认为
深度为3）。
若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(OrderedTree)；否则称为无序树(UnorderedTree)。注意：若不特别指明，一般讨论的树都是有序树。
森林(Forest)是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。对于图1的树而言，图2的两棵子树其实就可以理解为森林。树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。
对比线性表与树的结构，它们有很大不同，如图7所示。
图
图概述
图(Graph)是一种比线性结构和树形结构都要复杂的数据结构。简单讲，图是由表示数据元素的的集合V和表示数据之间关系的集合E组成。其中，数据元素常称作顶点(vertex)，数据之间的关系常称作边(edge)。故图可记为G=<V,E>，其中V是顶点的有穷非空集合，E是边的集合。在图中顶点的前驱和后继是不设限制的，因此图描述的是一种网状关系。
无向图
若边是无序的或者说是无向的，则称此图是无向图。若无向图中有边(vi,vj)(无向图中边用圆括号表示)，则显然(vj,vi)和(vi,vj)是同一条边。
有向图
若边是有序的或者说是有向的，则称此图是有向图。若有向图中有边<vi,vj>(有向图中边用尖括号表示)，则显然<vj,vi>和<vi,vj>不是同一条边。有向图中的边也称为弧(arc)，对于弧<vi,vj>，vi是弧尾(边的起点)，vj是弧头(边的终点)。
示例图
无向图 G1=<V1,E1> V1={v0,v1,v2,v3,v4} E1={(v0,v1),(v0,v2),(v1,v3),(v2,v3),(v2,v4),(v3,v4)}
有向图 G2=<V2,E2> V2={v0,v1,v2,v3} E2={<v0,v1>,<v0,v2>,<v2,v0>,<v2,v3>,<v3,v0>}
图的存储
所谓的图的存储，主要是想从存储结构中表达各顶点之间的联系，也就是表现图中的边。因为顶点总是很好存储的，如最常见的一维数组存储边：
顶点
| v0 | v1 | v2 | v3 | v4 |
或者是
| A | B | C | D | E
邻接矩阵(adjacency matrix)和邻接表(adjacency list)是图的两种常见存储方式。
如上，无向图G1，对于顶点Vi和顶点Vj，若有边，则(Vi,Vj)=1，否则(Vi,Vj)=0。显然(Vi,Vi)=0，此时的邻接矩阵如下：
显然，由于是无向图，该矩阵是对称的。邻接矩阵所需的存储空间的大小与边数无关，而与顶点数有关。它所需的空间复杂度是O(n^2)，n是顶点数。
同样的，若是使用邻接表来存储无向图G1，邻接表如下：
邻接表实质就是链式存储。
对于有权图，在邻接矩阵中只需把1改为为相应的权值即可，在邻接表中顶点结构体则需添加成员表示权值。
常用概念
环：在一条路径中，只有第一个顶点和最后一个顶点相同，这条路径就是环(cycle)或回路。
路径长度：路径上边的数目。
在有向图中，任意两个顶点之间都有一条有向的路径，则称该有向图是强连通图。
概论看不懂没关系.后面会用更简单的方法介绍.听起来吓人那就对了