稀疏矩阵存储

1. 三元组
2. 链式存储
3. 十字链表

栈实现

1. 顺序栈
2. 共享顺序栈(两个栈各自在一个数组的两端，向中间扩展)
3. 链栈

队列

1. 顺序队列
2. 循环顺序队列
3. 链
4. 优先队列
5. 双端队列

广义表

广义表(Lists，又称列表)是一种非连续性的数据结构，是线性表的一种推广

头尾表示法

有孩子的： 头指针、尾指针

无孩子的： 数据

孩子兄弟表示法

有孩子的：长子，兄弟

无孩子的：数据

火车进站入站问题

编号为1,2,3,4 的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如果 有n 列火车通过调度站，请设计一个算法，输出所有可能的调度结果。

解题思路：栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是1 ，2 ，3 ，4 全排列中的一个元素。由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：对于 序列中的任何一个数其后面所有比它小的数应该是倒序的，例如4321 是一个有效的出栈序列， 1423不是一个有效的出栈结果（4 后面比它小的两个数 2 ，3 不是倒序）。据此，本题可以通过 算法产生n 个数的全排列，然后将满足出栈规则的序列输出。

树和二叉树

• 在二叉树的第i层至多有2^(i-1)个节点
• 深度为k的二叉树至多有2^k-1个节点，k>=1
• n0=n2+1
• 具有n个节点的完全二叉树的深度为floor(logn)+1

树存储

1. 二叉链表
2. 三叉链表
3. 双亲链表
4. 孩子表示法

满二叉树和完全二叉树的区别：

1、完全二叉树是由满二叉树而bai引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

2、对于满二叉树，除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。而完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

树的表示方法

1.孩子兄弟表示法

class Node{
     int value;//结点中的数据域
     Node firstChild;//保存第一个孩子结点
     Node nextChild;//保存同一层的下一个兄弟结点
}

2.双亲表示法

用一组连续的空间来存储树中的结点，在保存结点的同时附设一个指示器指示其双亲结点在表中的wei

class TNode{
    int data;//值
    int parent;//父结点的下标`
}

3.孩子表示法

这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。n个结点共有n个孩子链表（叶子结点的孩子链表为空表），而n个结点的数据和n个孩子链表的头结点的头指针又组成一个顺序表。

//孩子链表结点的定义
class ChildNode{
    int child;//孩子结点在线性表中的位置
    ChildNode next;//下一个孩子结点
}
 
//顺序表结点的结构定义
class DataNode{
    int data;//结点的值
    ChildNode firstChild;//指向第一个孩子结点的引用
}
 
//树的定义
class ChildTree{
    DataNode nodes[MAX];//顺序表
    int root;//该树的根结点在线性表中的位置
    int num;//该树的结点个数
}

二叉树到树、森林的转换

树、森林与二叉树的转换

1、树转换为二叉树

由于二叉树是有序的，为了避免混淆，对于无序树，我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。

将树转换成二叉树的步骤是：
（1）加线。就是在所有兄弟结点之间加一条连线；
（2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；
（3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。

树转换为二叉树的过程示意图
2、森林转换为二叉树

森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。

将森林转换为二叉树的步骤是：
（1）先把每棵树转换为二叉树；
（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。

森林转换为二叉树的转换过程示意图
3、二叉树转换为树

二叉树转换为树是树转换为二叉树的逆过程，其步骤是：
（1）若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来；
（2）删除原二叉树中所有结点与其右孩子结点的连线；
（3）整理（1）和（2）两步得到的树，使之结构层次分明。

二叉树转换为树的过程示意图
4、二叉树转换为森林

二叉树转换为森林比较简单，其步骤如下：
（1）先把每个结点与右孩子结点的连线删除，得到分离的二叉树；
（2）把分离后的每棵二叉树转换为树；
（3）整理第（2）步得到的树，使之规范，这样得到森林。

根据树与二叉树的转换关系以及二叉树的遍历定义可以推知，树的先序遍历与其转换的相应的二叉树的先序遍历的结果序列相同；树的后序遍历与其转换的二叉树的中序遍历的结果序列相同；树的层序遍历与其转换的二叉树的后序遍历的结果序列相同。由森林与二叉树的转换关系以及森林与二叉树的遍历定义可知，森林的先序遍历和中序遍历与所转换得到的二叉树的先序遍历和中序遍历的结果序列相同。

图

无向图内：

如果任意两个顶点之间都能够连通，则称此无向图为连通图。

若无向图不是连通图，但图中存储某个子图符合连通图的性质，则称该子图为连通分量。

删除关节点会将一个连通分量分割成多个连通分量

没有关节点的连通图是重连通图

在重连通图中，只删除一个顶点及其相关联的边，肯定不会破坏其连通性。如果一味地做删除顶点的操作，直到删除 K 个顶点及其关联的边后，图的连通性才遭到破坏，则称此重连通图的连通度为 K 。如今的通信网络对人们的生活有着重要的影响，如果将通信网络比做一个巨大的连通图的话，它的连通度 K 值越高，证明其稳定性越好，即使某一个站点发生故障无法工作也不会影响整个系统的正常工作。

无向图求强连通分量直接挨个dfs即可。或者说无向图的连通分量都是强连通分量，因为边是双向的。

有向图：

有向图中，若任意两个顶点 Vi 和 Vj，满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就是都含有至少一条通路，则称此有向图为强连通图。

与此同时，若有向图本身不是强连通图，但其包含的最大连通子图具有强连通图的性质，则称该子图为强连通分量。

如果能从图的某一顶点出发，每条边恰好经过一次，这样的路线称为欧拉道路(Eulerian Path)。如果每条边恰好经过一次，且能回到起点，这样的路线称为欧拉回路(Eulerian Circuit)。

对于无向图G，当且仅当G 是连通的，且最多有两个奇点，则存在欧拉道路。如果有两个奇点，则必须从其中一个奇点出发，到另一个奇点终止。 如果没有奇点，则一定存在一条欧拉回路。

对于有向图G，当且仅当G 是连通的，且每个点的入度等于出度，则存在欧拉回路。如果有两个顶点的入度与出度不相等，且一个顶点的入度比出度小1，另一个顶点的入度比出度大1，此时，存在一条欧拉道路，以前一个顶点为起点，以后一个顶点为终点

哈密路回路是经过所有点。

图存储：

声明为共有变量

1. e[n][n]存储边花费，n个点

2. vector e[n]存储边花费，n个点

其他变量

1. vis[n]，存储是否识别，dfs、bfs、dijstra算法中需要

2. d[n]距离算法中需要

3. c[n][n]存储第二花费，最短路径第二花费最小问题

4. num[n]存储最短路径数量，最短路径个数问题

5. weight[n]存储各点权重，w[n]存储到各点的权和，最短路径最大权问题

DFS:

dfs(u) {
  vis[u] = true;
  for(从u除法道能到达的所有顶点v)
    if(vis[v] == false)
      dfs(v);
}
dfsTrave(G) {
  for(G的所有结点u)
    if(vis[u] == false)
      dfs(u);
}

//邻接矩阵
void dfs(int u, int depth) {
  vis[u] = true;
  for(int v = 0; v < n; v++) {
    if(vis[v] == false && G[u][v] != INF)
      dfs(v, depth + 1);
  }
}

void dfsTrave() {
  for(int u = 0; u < n; u++)
  	if(vis[u] == false)
    	dfs(u, 1);
}

//邻接表
void dfs(int u, int depth) {
  vis[u] = true;
  for(int u = 0; u < arr[u].size(); u++)
    dfs(v, depth + 1);
}

void dfsTrave() {
  for(int u = 0; u < n; u++) {
    if(vis[u] == false)
      dfs(u, 1);
  }
}

BFS

bfs(u) {
  queue q;
  将u入队
  inq[u] = true;
  while(q非空) {
    for(从u除法道可到达的所有定点v) {
      if(inq[v] == false)
        将v入队
        inq[v] = true;
    }
  }
}
bfsTrave(G) {
  for(G的所有顶点u) {
    if(inq[u] == false)
      bfs(u);
  }
}

void bfs(int u) {
  queue<int> q;
  q.push(u);
  inq[u] = true;
  while(!q.empty()) {
    int u = q.front();
    q.pop();
    for(int v = 0; v < n; v++) {
      if(inq[u] == false && G[u][v] != INF) {
        q.push(v);
        inq[v] = true;
      }
    }
  }
}
/*邻接表：
for(int i = 0; i < arr[u].size(); i++) {
  int v= arr[u][i];
  if(inq[u] == false) {
    q.push(v);
    inq[v] = true;
  }
}
*/

void bfsTrave() {
  for(int u = 0; u < n; u++) {
    if(inq[u] == false)
      bfs(q);
  }
}