• 增删改查判空判满

线性表

1．集合中必存在唯一的一个“第一元素”。
2．集合中必存在唯一的一个 “最后元素” 。
3．除最后一个元素之外，均有唯一的后继(后件)。
4．除第一个元素之外，均有唯一的前驱(前件)。

链表

• 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
• 链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
• 每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
• 相比于线性表顺序结构，操作复杂。
• 由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表顺序表相应的时间复杂度分别是O(logn)和O(1)。
• 其中存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。

循环链表

表中最后一个结点的指针域指向头结点，整个链表形成一个环。

双向链表

它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

栈（stack）

又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈的操作

链接

队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

链队列

• 所谓队列的链式存储结构是用一个线性链表来表示一个队列，队列中每一个元素对应链表中一个链结点，这样的队列简称链接队列。
• 具体地说，把线性链表第1个链结点的指针定义为队头指针front，在链表最后的链结点建立指针rear作为队尾指针，并且限定只能在链头进行删除操作，在链尾进行插入操作，这个线性链表就构成了一个链接队列。
• 另一个与顺序存储结构队列的不同点是，队头指针与队尾指针都是指向实际队头元素与队尾元素所在的链结点。
• 测试链接队列为空的条件是front为NULL。事实上，在链接队列中插人一个新的元素就是在链表的表尾链结点后添加一个新链结点；而删除一个元素的操作就是删除链表的第1个链结点。

循环队列

为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

串

串的全面解析

数组

1.数组是相同数据类型的元素的集合。
2.数组中的各元素的存储是有先后顺序的，它们在内存中按照这个先后顺序连续存放在一起。
3.数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如，a[0]表示名字为a的数组中的第一个元素，a[1]代表数组a的第二个元素，以此类推。

广义表

• 广义表(Lists，又称列表)是一种非线性的数据结构，是线性表的一种推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。
• D=(a，D)=(a，(a，(a，(…)))) D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。
• 一个表的"深度"是指表展开后所含括号的层数。

树

树（tree）是包含n（n>=0）个结点的有穷集，其中：
（1）每个元素称为结点（node）；
（2）有一个特定的结点被称为根结点或树根（root）。
（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。

二叉树

二叉树百度百科

• 一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。
• 而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。
• 具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子结点，至多有2k-1个结点。
• 完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
• 满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
• 平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

图

邻接表

邻接表

十字链表

邻接多重表

链接

最小生成树

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。

2.二叉树的结点

链接

计算二叉树所有结点的个数

各种遍历法

计算叶子结点的个数

1)当树为空时，叶子结点个数为0

2)当某个节点的左右子树均为空时，表明该结点为叶子结点，返回1

3)当某个节点有左子树，或者有右子树时，或者既有左子树又有右子树时，说明该节点不是叶子结点，因此叶结点个数等于左子树中叶子结点个数 加上 右子树中叶子结点的个数

计算满节点的个数（对于二叉树而言，满节点是度为2的节点）

1)当树为空时，满节点个数为0

2)当树中只有一个节点时，满节点个数为0

3)当某节点只有左子树时，需要进一步判断左子树中是否存在满节点

4)当某节点只有右子树时，需要进一步判断右子树中是否存在满节点

5)当某节点即有左子树，又有右子树时，说明它是满结点。但是由于它的左子树或者右子树中可能还存在满结点，因此满结点个数等于该节点加上该节点的左子树中满结点的个数 再加上 右子树中满结点的个数。
对于二叉树而言，有一个公式：

• 度为2的结点个数等于度为0的结点个数减去1。 即：n(2)=n(0)-1

3.二分查找

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

时间复杂度

假设其数组长度为n，经过m次二分查找到结果（即只剩下一个元素），则：n/(2^m) = 1（即n=m^2）。

其算法复杂度为o(log(n))

最大查找次数

最坏情况下次数：logN+1（logN向下取整）

4.各种排序情况

5.图的各种定义，结点和边的关系

n个结点，至少有n-1条边

6.散列函数（Hash）

一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
例如：一组线性表进行散列存储，散列函数即是：H（K） = K % 9，那么最后的散列地址（本题为余数）为n的元素，有…个

Hash查找

链接

Hash表

链接

7.广义表转化成树

例如：假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树的度为_________

• 因为广义表本身是“嵌套”，这个表这么看：
  根是A，有三个孩子C,D,H
  D有三个孩子E,F,G
  H有两个孩子I,J
  根据这个结构就可以确定一颗树了，度为3（根节点的度）.

8.前缀后缀表达式

链接

前缀

• 例如，(a+b) * (c+d)转换为 *,+,a,b,+,c,d。
• 后面的前缀表达式的运算方式为：如果当前字符(或字符串)为数字或变量，则压入栈内；如果是运算符，则将栈顶两个元素弹出栈外并作相应运算，再将结果压入栈内。当前缀表达式扫描结束时，栈里的就是中缀表达式运算的最终结果。

后缀

(a+b)c的逆波兰式为ab+c

1）a入栈（0位置）
2）b入栈（1位置）
3）遇到运算符“+”，将a和b出栈，执行a+b的操作，得到结果d=a+b，再将d入栈（0位置）
4）c入栈（1位置）
5）遇到运算符“”，将d和c出栈，执行dc的操作，得到结果e，再将e入栈（0位置）
经过以上运算，计算机就可以得到(a+b)*c的运算结果e了。

• 例如：8-(3+2*6)/5+2^2
• 前缀表达式：+ ^ 2 2 - / 5 + * 6 2 3 8
• 后缀表达式：8 3 2 6 * + 5 / - 2 2 ^ +

9.树的指针域

• 例如：一棵有n个结点采用链式存储的二叉树中，共有（ ）个指针域为空。
• 每个节点有两个指针（左右指针），所以其有2n个指针用于指向孩子节点
  除根节点外，每出现一个节点会占用其父节点的一个指针域，所以占据n-1个指针域
  所以剩下的空指针域为2n-(n-1)=n+1

10.邻接表&邻接矩阵

链接

11.Kruskal 和 Prim

Kruskal（边）

链接
在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。

1.将图的所有连接线去掉，只剩顶点

2.从图的边集数组中找到权值最小的边，将边的两个顶点连接起来

3.继续寻找权值最小的边，将两个顶点之间连接起来，如果选择的边使得最小生成树出现了环路，则放弃该边，选择权值次小的边

4.直到所有的顶点都被连接在一起并且没有环路，最小生成树就生成了。

Prim（点）

链接
从带权连通图的任意顶点开始，如顶点A，
将该顶点放入集合V中，然后从与A相连的顶点中找到一个顶点B,使得边的权值最小，
将B也放入集合V中，边（A,B）就是最小生成树的一条边。
接着再从顶点中找到顶点C使得C到集合V的边权值最小（即到A或B的权值最小）。
按照这种步骤继续下去，直到所有的顶点都被访问过。

11.B树详解

B树详解

12.二叉搜索树的查找

在二叉搜索树b中查找x的过程为：

1. 若b是空树，则搜索失败，否则：
2. 若x等于b的根节点的数据域之值，则查找成功；否则：
3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：
4. 查找右子树。

// 在根指针T所指二叉查找树中递归地查找其关键字等于key的数据元素，若查找成功，
// 则指针p指向該数据元素节点，并返回TRUE，否则指针指向查找路径*问的最终
// 一个节点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL
Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){

  if(!T) { //查找不成功
    p=f;
    return false;
  }
  else if (key == T->data.key) { //查找成功
    p=T;
    return true;
  }
  else if (key < T->data.key) //在左子树中继续查找
    return SearchBST(T->lchild, key, T, p);
  else //在右子树中继续查找
    return SearchBST(T->rchild, key, T, p);
}

13.哈夫曼树（最优二叉树）

画法

14.筛选法建立初始堆

链接

15.DFS BFS

链接

16.二叉排序树

链接

17.已知边集求图的拓扑序列

• 设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为？
  我觉得是1-4-3-2 为什么答案是1-4-2-3呢,还是说拓扑排序可以有很多种写法呢？2-3不是冲突了吗？！
  答案是1-4-2-3，对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。

通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。

例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。

扩展资料：

拓扑排序主要思想
有向图可以拓扑排序的条件是：图中没有环。
具体方法：
1、 从图中选择一个入度为0的点加入拓扑序列。
2、从图中删除该结点以及它的所有出边（即与之相邻点入度减1）。
反复执行这两个步骤，直到所有结点都已经进入拓扑序列，若图中存在回路，拓扑排序无法进行。