计算机网络的坑还没有填完，于是我决定开个新坑。
二刷完了数据结构，来一个粗暴的整理。
高能慎入，只是简单的总结，并没有复杂的推导过程和代码。
数据结构
程序设计 = 算法 + 数据结构。数据：描述事物的符号，可以输出计算机并处理。数据元素：组成数据的有意义的基本单位。人群中的数据元素就是人。数据项：描述数据元素的最小单位，不可切分。数据对象：性质相同的数据元素的结合，是数据的子集。数据结构：相互之间存在一种或多种特定关系的数据元素的集合。数据类型：性质相同的值的集合及定义在上面的操作。抽象数据类型：一个数学模型及在上面的操作。
逻辑结构面向问题，物理结构面向计算机
逻辑结构
图、树、集合、线性结构。线性结构中常用的为：队列、栈、线性表。
物理结构
顺序存储：如数组，逻辑关系和物理关系对应。
链式存储：逻辑关系和物理关系无关，逻辑相邻，物理不相邻。靠存储单元中的指针指向下一个地址。
算法
算法的特性
输入输出：可以没有输入，但至少有一个输出有穷性：可接受的时间内求解确定性：对于任何输入或相同输入，得到唯一确定的解可行性：有限步骤内求解问题
算法的目标
正确性：算法的输出是正确的，通常用数学的方法证明可读性：通俗易懂健壮性：面临任何极端输入，都能得到确定的输出时间存储：算法执行时间快，需要的存储空间少
时间复杂度
算法的渐进增长取决于最高项，执行次数$T(n)$是关于问题规模$n$的函数，$T(n)=O(f(n))$，增长率和$f(n)$相同，称为渐进时间复杂度，也叫时间复杂度，只保留最高项，去除常熟和系数。
最坏情况的时间复杂度是算法的保证，代码中辅助存储空间的空间复杂度一律为$O(1)$。
线性表
零个或多个相同类型的数据元素组成的有限序列（一个数据元素可以包括多个数据项）。
顺序结构：存取为$O(1)$，不能为逻辑关系的增加设置额外的存储空间。插入与删除为$O(n)$，主要是元素的移动。难以确定容量，可能会造成内存空间的碎片。
链式结构：头指针指向下一个元素，最后节点的指针为空。存取的复杂度为$O(n)$，并不知道元素的位置在哪里，插入删除的时间复杂都为$O(1)$。整表的删除与创建，头插入，尾插入，需要借助两个指针。
静态链表：数组表示链式线性表。使用数组式结构体，每个数组有两个值，一个表示本节点的值，一个表示下一个节点在数组中的位置。
循环链表：尾指针指向头指针。
双向链表：节点加入前驱后继。
栈
也属于线性表，只能在表尾进行插入和删除，表尾也是栈顶。顺序存储使用数组，链式存储使用指针，结构体存储指向自己的指针和值。
两栈共享空间，当两个栈顶指针重合时栈溢出。
栈的应用，递归。递归易懂，但是迭代不用占用额外的存储空间。
递归, 每次递归都会产生调用栈，不在可执行文件中，在执行时创建。调用栈所在的段为堆栈段，有自己的大小不能越界访问，否则为段错误。每次递归会在调用栈里增加一个栈帧，越界后的错误为栈溢出。
后缀表达式的应用：也称为逆波兰表达式，Reverse Polish Notation。无括号表达式。数字压栈，遇到操作符取出来，后者操作前者。
中缀表达式转后缀：是正常的小学算术的四则运算。1.数字直接输出。2.遇到)，输出遇到第一个(之间所有的符号。3.(直接压栈。4.后来者优先级高则压栈，优先级低，弹两个。完成转后缀表达式。
队列
一端进，一端出，先进先出。如操作系统的任务序列，键盘输入到记事本的显示同样为队列。简单的顺序存储会造成存储资源的浪费，循环队列可以对空白位置利用。位置计算(rear+1)%QueueSize==front。链式结构同样，先进先出，包括了指针与值。
串
零个字符或多个字符组成的有限序列，序列表明了元素的前驱后继的关系。子串的位置：子串对应到主串中，第一个字符的位置。顺序存储：”\0”表示结束，不计入长度。链式存储：一个节点可以存储多个字符。朴素匹配：最好的复杂度为$O(1)$，平均复杂度为$O(m+n)$，最坏为$O((n-m+1)\cdot m)$KMP匹配： 两个步骤，根据字符串中重复元素计算next数组，根据next数组计算字串中$j$的位置。主串中的$i$不回溯提高效率。
计算next方法：$next[1]=0,next[j]=max\{k|p_{k+1}=p_{j-k+1}\}$，其余情况为1。时间复杂度为$O(m+n)$。在许多部分匹配下能体现优势。
树
基本概念
一对多的层次关系，有限集合，结点$n\geq 0$。根节点下的子树没有交集，不构成环。
节点的度：节点拥有孩子的数量称为节点的度。所有节点中最大的度为树的度。度为0是叶子节点或，度不为0的非根节点是分支节点。树的深度：根在第一层，根的孩子是第二层，依次类推到树中的最大层，得到树的深度。森林：多个不相交的树的结合。节点的关系：节点的子树称为节点的孩子，节点是子树的父亲。
如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
存储方式：树的表示方法多种多样，如一个域存数值，或者一个域存指向父亲的指针，或者一个域指向多个孩子节点，或者有几个孩子就有几个域，然后指针指过去。实现方法多种多样，需要根据实际情况加以调整。
二叉树
二又树（Binary Tree）是$n(n\geq 0)$个结点的有限集合，该集合或者为空集（称为空二叉树）。
或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
不存在度大于2的节点，左右子树的顺序不能任意交换，交换后不是相同的二叉树，严重区分左右。
五种形态：1.空二叉树。2.只有一个节点。3.只有左子树。4.只有右子树。5.左右子树都有。
特殊二叉树
斜二叉树：只有左二叉树或只有右二叉树。满二叉树：所有分支节点都存在左子树和右子树。所有叶子节点在同一层。同深度的二叉树中，满二叉树的节点数最多。非叶节点度数必须为2。完全二叉树：从上到下，从左到右开始编号，和满二叉树完全对应。叶子节点在最下两层。最下层的叶子在左边。不存在只有右孩子而不存在左孩子的情况。
二叉树的性质
1.二叉树的第$i$层至多有$2^{i-1}$个节点。2.深度为$k$的二叉树之多有$2^k-1$个节点，等比序列求和。3.二叉树中，终端节点的数量等于节点为2的数量+1。4.具有$n$个节点的完全二叉树的深度为$\lfloor \log_2 n\rfloor+1$。5.完全二叉树中，从1开始编号，节点乘以2是左节点，乘以2在加1是右节点。
遍历二叉树
二叉树的遍历（traversing binary tree）是指从根结点出发，接照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。前序遍历：先根节点，然后左子树，然后右子树。中序遍历：先左子树，然后根节点，然后右子树。后序遍历：先左子树，然后右子树，然后根节点。层序遍历：先上后下，先左后右。
线索化二叉树：以某种顺序遍历二叉树，在两端的指针域使得节点直接指向遍历顺序的前驱后继，将二叉树变为线索化二叉树，按照指针的顺序遍历则得到了双向链表。用于经常访问节点的前驱后继时使用。
树、森林、二叉树的转换
树到二叉树：兄弟节点之间加入连线。去除父节点与所有有孩子的连线。森林到二叉树：每个树转为二叉树。右边的树作为左边树的右孩子插入。二叉树转为树：父亲节点与所有的右孩子连线。去除原来的父节点与孩子节点的连线。二叉树转森林：从根节点开始，删除与右子树的连线。以删除后右子树的根开始，再删除与右子树的连线。得到多个独立的二叉树，这些二叉树在转树。
哈夫曼树
带权路径长度最小的二叉树。距离的计算为：从根节点出发(不包括根节点，不带权时包括分支节点，带权时不包括)，达到目标节点的路径长度是经过的节点的数量。如果带有权值就乘上。哈夫曼树的二叉树路径最小。
哈夫曼树生成过程，挑选权重最小的两个节点组成新节点。新节点在和其余最小的节点组成新节点，以此类推。
哈夫曼编码可以实现文件压缩，按照频率实现哈夫曼树，左0右1。保证一个编码不是另一个编码的前缀。
图
图的基本概念
顶点集合不为空，但有穷，以及顶点之间的边。表示为$G=(V,E)$，$V$表示顶点集合，$E$表示顶点之间边的结合。边表示的是顶点之间的逻辑关系。
顶点之间没有方向称为无向边。顶点$v_1$到$v_2$有方向，称为弧，$v_1$是弧尾，$v_2$是弧头。无向边用圆括号记录，弧使用尖括号记录，<弧尾，弧头>。简单图：不存在重复的边，不存在自己指向自己的边。无向完全图：任意的两个顶点都存在边。共$n\times (n+1)/2$条边。有向完全图：任意两点之间存在两条方向相反的弧。共$n\times (n+1)$条边。稀疏图：边比较少。反之称为稠密图。网：带权图通常称为网。子图：对于$G’=(V’,E’)$和$G=(V,E)$有$V’\in V,E’\in E$，称为$G’$是$G$的子图。图与顶点之间的关系：无向图中，顶点$v$的度是与顶点$v$相关联的边的数目，边的数量是度数和的一半。有向图中，入度是顶点作为弧头的数量，出度反之，出度=入读=边的数量。
路径长度是路径上边的数量。
路径中顶点不重复称为简单路径，或者简单环。连通图：任意两个顶点是联通的。极大连通子图：连通的子图，含有极大顶点数和依赖这些顶点的边。也成为连通分量。强连通图：有向图中任意两点存在路径，强连通分量计为其子图。生成树：连通图的极小连通子图。含有全部$n$个顶点，足以构成$n-1$条边的树。有向树：一个顶点没有入度，其余顶点入度是1。有向图的生成森林：若干有向树，全部顶点，若干弧。
存储结构：顶点的邻接点之间不存在次序关系。对于邻接矩阵，矩阵的两个维度都是顶点，以1表示边存在，0表示不存在。是一个对角线为零的对称矩阵，行列可求度。有向图的邻接矩阵中，对角线为0，$\infty$表示不存在。邻接矩阵的时间复杂度为$O(n^2+n+e)$，初始化，读边，读点。
降低时间复杂的的操作为邻接表，无论是有向图还是无向图，存储方式都是从顶点出发，一个指针域指向下一个节点。时间复杂度为$O(n+e)$，读点，插边。
图的结构
图的遍历指每个节点仅仅被访问一次。深度优先和广度优先，是一个递归的过程。
最小生成树算法：Prim：$O(n^2)$，Krsukal：$O(e\log e)$。图的拓扑序列：顶点是事件的开始，弧为优先序列，表示为AOV网，将有向图构造为拓扑序列。顺序不存在回路，描述活动的制约关系。
边上有权表示为AOE网，无条件制约，但是求路径的权重最大或最小，如网络最大流问题。（建立反向路径）。
查找
查找表：是同一类型的数据元素构成的集合，一主关键字区分，查找后对应的关键字相等。静态查找：只查找，不删除也不插入。动态查找：可以考虑改变数据元素的关系改善查找性能。
线性表的查找$O(n)$，折半查找$O(\log n)$。索引：将关键字与对应的记录关联，索引项可以构成线性结构。稠密索引：索引等于数据规模的长度。分块索引：块内无序，块间有序，用于数据库，复杂度$O(\sqrt n)$。倒排索引：属性值决定记录的位置，用于搜索引擎。二叉排序树：中序遍历有序，左子树小于根，右子树大于根。查找时按顺序查找即可，插入时按顺序插入，删除时叶节点直接删除，只有左子树或右子树则子承父业，左右子树都存在时，中序遍历寻找删除节点的直接前驱与后继，代替原来的节点。平衡二叉树：平衡因子为BF，左子树深度减去右子树深度即可得到。平衡因子绝对值大于1，用于频繁的插入与删除，插入、删除、查找均为$O(\log n)$。旋转调整时均以失衡点下一个点为中心。
| 左左 | 右右 | 右左 | 左右 |
|---|---|---|---|
| 右旋 | 左旋 | 右旋，左旋 | 左旋，右旋 |
多路查找树
2-3树：每个节点有两三个孩子。二节点，一个元素，两个孩子或者没有孩子（左小右大，不能只有一个孩子）。一个三节点，一小一大两个元素，三个孩子或没有孩子。插入与删除的时候，可以有单个叶节点。空树插入为二节点，在插入为三节点。删除时三节点拆分，或者二节点上移。看情况讨论，极为复杂。2-3-4树：4节点三个元素，只有四个孩子或者没有孩子。B树：平衡的多路查找树，节点最大的孩子数目为B树的阶，非叶节点至少两个孩子。每个非根的分支节点$k$个元素和$k-1$个孩子，每个叶节点有$k-1$个元素，所有叶子节点位于同一层。减少了访问数据块的次数，即IO次数，提高了性能。B+树：弥补了B树的缺陷，中序遍历防止多次遍历根节点。所有叶子节点接在一起，即根节点在叶节点中再次出现，自小到大排列好，查找高效$[18,+\infty)$，插入与删除都在叶节点。（因为根节点已经下来了）。
散列表
也叫哈希。存储位置=f（关键字），对应的存储空间称为哈希表，数据元素没有逻辑关系。适合存储与查找，需要考虑关键字的长度，函数需要的时间，是否分布均匀。函数要求计算简单，可以处理冲突，散列地址分布均匀，如平方取中，数字分析。面临冲突时线性探测或者链式解决。查找的复杂度为$O(1)$。
散列表的平均查找长度取决于填充因子，填入个数除以总长度，不取决于填入元素的总长度。
排序
稳定排序：排序之前$r_1$先于$r_2$，在排序之后$r_1$仍然先于$r_2$。
给个不错的链接：https://hit-alibaba.github.io/interview/basic/algo/Sorting.html
| 稳定排序 | 不稳定排序 |
|---|---|
| 冒泡排序 $O(n^2 )$ | 快速排序 $O(n\log n)$ |
| 插入排序 $O(n^2 )$ | 堆排序 $O(n \log n)$ |
| 桶排序 $O ( n ) $ | 希尔排序 $O(n \log n)$ |
| 归并排序 $O(n \log n)$ | 选择排序 $O( n^2 )$ |
文字的过程，让思考沉淀。
