---

一、时间复杂度

1. 算法时间复杂度以算法中基本操作重复执行的次数(简称为频度)作为算法的时间度量。一般不必要精确计算出算法的时间复杂度,只要大致计算出相应的数量级即可。
   
2. 计算规则

• 加法规则:多项相加，保留最高阶项，并将系数化为1
• 乘法规则:多项相乘都保留，并将系数化为1
• 加法乘法混合规则:小括号再乘法规则最后加法规则

3. 渐进符号
   
4. 递归的事件复杂度，空间复杂度
   (1)展开式
   事件复杂度=递归次数 x 每次递归的时间复杂度
   (2)主观法
   

二、线性结构

线性结构是一种基本的数据结构，主要用于对客观世界中具有单一前驱和后继的数据关系进行描述。线性结构的特点是数据元素之间呈现一种线性关系，即元素“一个接一个排列”

2.1 线性表

线性表是最简单、最基本也是最常用的一种线性结构。常采用顺序存储和链式存储，主要的基本操作是插入、删除和查找等。

一个线性表是 n(n≥0)个元素的有限序列

非空线性表的特点
(1)存在唯一的一个称作“第一个”的元素。
(2)存在唯一的一个称作“最后一个”的元素。
(3)除第一个元素外，序列中的每个元素均只有一个直接前驱。
(4)除最后一个元素外，序列中的每个元素均只有一个直接后继。

2.2线性表存储结构

线性表的存储结构分为顺序存储和链式存储。
（1）线性表的顺序存储
线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

• 在表长为n的线性表中插入新元素时，共有n+1个插入位置，新元素在n+1个位置插入的概率相同时，插入一个新元素需要移动的元素个数期望值 E为n/2。时间复杂度最好O(1)，最坏O(n)，平均O(n)
• 等概率下删除元素时需要移动的元素个数期期望值 E为(n-1)/2。时间复杂度最好O(1)，最坏O(n)，平均O(n)
• 最好，最坏，平均的时间按复杂度都是O(1)

（2）线性表的链式存储
①时间复杂度

时间复杂度	插入	删除	查询
最好	O(1)	O(1)	O(1)
最坏	O(n)	O(n)	O(n)
平均	O(n)	O(n)	O(n)

②存储密度不高

2.3栈

（1）栈是只能通过访问它的一端来实现数据在储和检索的一种线性数据结构。
（2）入栈和出栈都不需要遍历列表
（3）递归
（4）先进后出，后进先出

2.4队列

（1）队列是一种先进先出的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中,允许插入元素的一端称为队尾(Rear)允许删除元素的一端称为队头(Front)。
（2）入队和出队都不需要遍历列表
（3）循环队列的优点，入队出队都不需要移动其他元素

2.5串

（1）概念

• 空串:长度为零的串称为空串，空串不包含任何字符。
• 空格串:由一个或多个空格组成的串。虽然空格是一个空白字符，但它也是一个字符,在计算串长度时要将其计算在内。
• 子串:由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串。子串在主串中的位置是指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。
• 串相等:指两个串长度相等且对应序号的字符也相同。
• 串比较:两个串比较大小时以字符的ASCI码值(或其他字符编码集合)作为依据。实质上，比较操作从两个串的第一个字符开始进行，字符的码值大者所在的串为大:若其中一个串先结束，则以串长较大者为大。
  （2）模式匹配
  ①时间复杂度
  n主串，m模式串
  最好O(m)，最坏O(n*m)，平均O(n+m)
  ②KMP
  串的前缀：包含第一个字符并且不包含最后一个字符的字串
  串的后缀：包含最后一个字符并且不包含第一个字符的字串
  第i个字符的next值 =从1~(i-1)串中最长相等前后缀长度+1
  特殊情况:next[1]=0

2.6数组

1. 一维数组
   LOC:第一个元素的首地址，L:元素大小
   下标从0开始：ai=LOC+ixL
   下标从1开始：ai=LOC+(i-1)xL
2. 二维数组
   LOC:第一个元素的首地址、N:行数、M:列数、L:元素大小
   按行优先存储并且下标从0开始：aij=LOC+(ixM+j)xL
   按行优先存储并且下标从1开始：ai,j=LOC+[(i-1)xM+(j- 1)]xL
   按列优先存储并且下标从0开始：aii=LOC+(jxN+i)xL
   按列优先存储并且下标从1开始：aij=LOC+[(j-1)xN+(i-1)]xL

2.7矩阵

1. 对称矩阵
   ①Aᵢⱼ=Aⱼᵢ
   ②地址
   i>=j
   下标从0开始：Aᵢ,ⱼ = i(i+1)/2+j+1
   下标从1开始：Aᵢ,ⱼ = i(i-1)/2+j
   i=<j
   下标从0开始：Aᵢ,ⱼ = j(j+1)/2+i+1
   下标从1开始：Aᵢ,ⱼ = j(j-1)/2+i
2. 三角对称矩阵
   按行存储
   下标从0开始：Aᵢ,ⱼ = 2i+j+1
   下标从1开始：Aᵢ,ⱼ = 2i+j-2
3. 稀疏矩阵
   稀疏矩阵的三元组表的顺序存储结构称为三元组顺序表，常用的三元组表的链式存储结构是十字链表。

2.8树

1. 概念
   (1)双亲、孩子和兄弟。结点的子树的根称为该结点的孩子;相应地，该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟。
   (2)结点的度。一个结点的子树的个数记为该结点的度。
   (3)叶子结点。叶子结点也称为终端结点，指度为0的结点。
   (4)内部结点。度不为0的结点，也称为分支结点或非终端结点。除根结点以外，分支结点也称为内部结点。
   (5)结点的层次。根为第一层，根的孩子为第二层，依此类推，若某结点在第i层，则其孩子结点在第 i+1 层。
   (6)树的高度。一棵树的最大层数记为树的高度(或深度)
2. 性质
   性质1：树中的结点总数等于树中所有结点的度数之和加1
   性质2：度为 m 的树中第i层上最多有 mⁱ⁻¹个结点(i>1)
   性质3：高度为 h的 m 次树最多有(mʰ-1)/(m-1)个结 点
   性质 4:具有n个结点、度为m的树的最小高度为 [logₘ(n(m-1)+1)] (上取整)
3. 二叉树
   分为左右子树，二叉树的节点最大为2
   二叉树性质1：二叉树第层(i≥1)上最多有2ⁱ⁻¹个结点
   二叉树性质2：高度为h的二叉树最多有2ʰ-1个结点
   二叉树性质3：对于任何一棵二叉树，度为0的结点数等于度为2的结点数+1
   二叉树性质4：具有几个结点的完全二叉树的高度为[log₂n]+1(下取整)或[log₂(n+1)]（上取整）
4. 满二叉树
   深度为k的二叉树有2ᵏ-1个结点，则称其为满二叉树
   
5. 完全二叉树
   深度为k、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应

• 当节点数确定时，完全二叉树的高度最小

6. 平衡二叉树
   ①二叉树中的任意一个结点的左右子树高度之差的绝对值不超过1
   ②完全二叉树一定是平衡二叉树，平衡二叉树不一定是完全二叉树
   ③叶子节点满足平衡二叉树的条件要求
7. 二叉排序树
   ①根结点的关键字

• 大于左子树所有结点的关键字，
• 小于右子树所有结点的关键字，
• 左右子树也是一颗二叉排序树

中序遍历得到的序列是有序序列

②查找效率最差的是单支树
8. 最优二叉树（哈夫曼树）
①最优二叉树又称为哈夫曼树，它是一类带权路径长度最短的树。路径是从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。
②树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权值的乘积。
n为带权叶子结点数目，wk为叶子结点的权值，lk为叶子结点到根的路径长度。

③何构造最优二叉树

构造最优二叉树的哈夫曼算法如下
    (1)根据给定的个权值{w1，w2，…,wn}，构成n棵二叉树的集合 F={T1,T2,…,Tn}，其中,每棵树Ti中只有一个带权为wi的根结点，其左、右子树均空。
    (2)在F中选取两棵权值最小的树作为左、右子树构造一棵新的二叉树，置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。
    (3)从F中删除这两棵树，同时将新得到的二叉树加入到F中。
    重复(2)、(3)步，直到F中只含一棵树时为止，这棵树便是最优二叉树(哈夫曼树)。
    由此算法可知，以选中的两棵子树构成新的二叉树，哪个作为左子树，哪个作为右子树，并没有明确。所以，具有n个叶子结点的权值为 w1,w2,…,wn 的最优二叉树不唯一，但其 WPL值是唯一确定的。

④哈夫曼编码
若对每个字符编制相同长度的二进制码则称为等长编码。左0右1

2.9二叉树的存储结构

1. 二叉树的顺序存储结构
   假设有编号为i的结点，则有:
   若 i=1，则该结点为根结点，无双亲;若i>1，则该结点的双亲结点为[i/2]
   若 2i <= n，则该结点的左孩子编号为2i，否则无左孩子。
   若 2i+l1<=n，则该结点的右孩子编号为 2i+1，否则无右孩子。
   在最坏情况下，一个深度为k且只有k个结点的二叉树(单支树)需要2ᵏ-1个存储单元。
2. 二叉树的链式存储结构
   ①n个节点有2n个指针域
   ②n个节点有n-1个分支

2.10二叉树遍历

1. 先序遍历
2. 中序遍历
3. 后序遍历
4. 层次遍历
5. 先序遍历+中序遍历可构造二叉树
6. 后序遍历+中序遍历可构造二叉树
7. 层次遍历+中序遍历可构造二叉树
8. 先序遍历+后序遍历不可构造二叉树

2.11图

1. 定义
   图是由集合V和E构成的二元组,记作G=(V，E)，其中，V是图中顶点的非空有限集合,E是图中边的有限集合。
   
2. 有向图，无向图

(1)有向图。若图中每条边都是有方向的，那么顶点之间的关系用<vi,vj>表示，它说明从vi到vj有一条有向边(也称为弧)。vi是有向边的起点，vj称为弧尾;是有向边的终点，称为弧头。所有边都有方向的图称为有向图。
(2)无向图。若图中的每条边都是无方向的，顶点vi和vj之间的边用(vi,vj)表示。因此，在有向图中<vi,vj>与<vj,vi>分别表示两条边，而在无向图中(vi,vj)与(vj,vi)表示的是同一条边。

3. 完全图
   若一个无向图具有n个顶点，而每一个顶点与其他n-1个顶点之间都有边则称之为无向完全图。显然，含有n个顶点的无向完全图共有n(n-1)/2条边。类似地，有 n 个顶点的有向完全图中弧的数目为 n(n-1),即任意两个不同顶点之间都有方向相反的两条弧存在。
4. 度、出度和入度。
   预点v的度是指关联于该顶点的边的数目，记作 D(v)。若G为有向图，顶点的度表示该顶点的入度和出度之和。顶点的入度是以该顶点为终点的有向边的数目，而顶点的出度指以该顶点为起点的有向边的数目，分别记为 ID(v)和 OD(v)。无论是有向图还是无向图，顶点数 n、边数e与各顶点的度之间有以下关系。
   
5. 路径。
   在无向图 G 中，从顶点vp到顶点vq的路径是指存在一个顶点序列vp，vi1，vi2，…，vin，vq，使得(vp，vi1)，(vi1，vi2)，…，(vin，vq)均属于E(G)。若G是有向图，其路径也是有方向的，它由 E(G)中的有向边<vp,vi1>,<vi1，vi2>,…,<vin，vq>组成。路径长度是路径上边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或环。若一条路径上除了vp和vq可以相同外，其余顶点均不相同，则称其为简单路径。
6. 连通图与连通分量。
   在无向图G中，若从顶点vi到顶点vj有路径，则称顶点vi和顶点vj是连通的。如果无向图 G中任意两个顶点都是连通的，则称其为连通图。无向图G的极大连通子图称为G的连通分量。
7. 强连通图与强连通分量。
8. 在有向图G中，如果对于每一对顶点vi,vj∈V且vi不等于vj,从顶点vi到顶点vj和从顶点vj到顶点vi都存在路径，则称图G为强连通图。有向图中的极大连通子图称为有向图的强连通分量。
9. 图的存储结构
   图的基本存储结构有邻接矩阵表示法和邻接链表表示法两种
   （1） 邻接矩阵表示法

图的邻接矩阵表示法是指用一个矩阵来表示图中顶点之间的关系。对于具有n个顶点的图G(V.E)，其邻接矩阵是一个n阶方阵，且满足:

（2）邻接链表表示法

邻接链表表示法指的是为图的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边(对于有向图是以vi为尾的弧)。邻接链表中的结点有表结点(或边结点)和表头结点两种类型，如下所示:

10. 稠密图，稀疏图
    稠密图用邻接矩阵来存，稀疏图用邻接表存
11. 网
    边(或弧)带权值的图称为网

拓扑排序
vi在vj之前
可能存在<vi,vj>，一定不存在<vj,vi>
对 AOV网进行拓扑排序的方法如下。
(1)在 AOV网中选择一个入度为0(没有前驱)的顶点且输出它。
(2)从网中删除该顶点及与该顶点有关的所有弧。
(3)重复上述两步，直到网中不存在入度为0的顶点为止。

12. 图的遍历
    ①深度优先

时间复杂度	邻接表	邻接矩阵
广度深度一样	O(n^2)	O(n+e)

②广度优先

三、查找

3.1基本概念

静态：查询，检索数据
动态：插入，删除数据
静态查找表有：顺序查找，折半(二分)查找，分块查找
动态查找表有：二叉排序树，平衡二叉树，B树，哈希表

3.2顺序查找

1. 从前往后，顺序查找
2. 顺序查找适应于顺序存储，链式存储
3. ASL=(n+1)/2

3.3折半查找（二分查找）

1. 设查找表的元素存储在一维数组r[1,…,m]中，在表中的元素已经按关键字递增方式排序的情况下，进行折半查找的方法是:首先将待查元素的关键字(Key)值与表r中间位置上(下标为 mid)记录的关键字进行比较，若相等，则查找成功;若 key>r[mid].key，则说明待查记录只可能在后半个子表 r[mid+1,…,m]中，下一步应在后半个子表中进行査找;若 key<r[mid].key,说明待查记录只可能在前半个子表r[1,…,mid-1]中，下一步应在r的前半个子表中进行查找,这样逐步缩小范围，直到查找成功或子表为空时失败为止。
2. 比较最多查找次数：[log₂n]+1(下取整)
3. ASL=(log₂(n+1))-1
4. 时间复杂度O(log₂n)

3.4哈希查找

1. 根据设定的哈希函数 H(key)和处理冲突的方法,将一组关键字映射到一个有限的连续的地址集(区间)上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表，这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。
2. 对于某个哈希函数 日和两个关键字 K, 和 K,，如果 K,≠K,，而 H(K,)=H(K)，则称为冲突。具有相同哈希函数值的关键字对该哈希函数来说称为同义词。
3. 构造哈希函数（除留取余法）
   H(key)=key%m（m取值接近n，但不大于n的质数）
   尽可能使关键字的所有组成部分都能起作用
4. 处理冲突法

①开发地址法

②链地址法

5. 哈希查找
   冲突：关键字映射到相同的位置
   α=表中装入的记录数/哈希表的长度
   α标志着哈希表的装满程度。直观地看，α越小，发生冲突的可能性就越小;反之，α越大，表中已填入的记录越多，再填记录时，发生冲突的可能性就越大，则查找时，给定值需与之进行比较的关键字的个数也就越多。

3.4大顶堆，小顶堆

n个关键码构成的序列{k1,k2,…,kn}，当且仅当满足下列关系时称其为堆。

四、排序

4.1基本概念

①经排序获得递增或递减关系
②若在待排序的一个序列中，Ri和Rj的关键字相同，即ki=kj，且在排序前Ri领先于Rj，那么在排序后，如果Ri和Rj的相对次序保持不变，Ri仍领先于Rj，则称此类排序方法为稳定的。
③内部排序：内部排序指待排序记录全部存放在内存中进行排序的过程。
④复杂度

4.2直接排序

直接插入排序是一种简单的排序方法，具体做法是:在插入第i个记录时，R1、R2、…、Ri-1已经排好序，这时将的关键字k1依次与关键字ki-1 、ki-2等进行比较，从而找到应该插入的位置并将Ri插入，插入位置及其后的记录依次向后移动。

4.3希尔排序

希尔排序又称为“缩小增量排序”，它是对直接插入排序方法的改进。
希尔排序的基本思想是:先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。具体做法是先取一个小于 n的整数 d1, 作为第一个增量，把文件的全部记录分成di个组，即将所有距离为d1倍数序号的记录放在同一个组中,在各组内进行直接插入排序;然后取第二个增量 d2(d2<d1),重复上述分组和排序工作，依此类推，直到所取的增量 di=1(di<di-1 <…<d2<d1)，即所有记录放在同一组进行直接插入排序为止。

4.4简单排序

n个记录进行简单选择排序的基本方法是:通过n-(1<= i<=n)在次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换，当i等于n时所有记录有序排列。

4.5堆排序

4.6冒泡排序

冒泡排序：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此下去，直至最终完成排序 。

4.7快速排序

快速排序的基本思想（分治）是:通过一趟排序将待排的记录划分为独立的两部分，称为前半区和后半区，其中，前半区中记录的关键字均不大于后半区记录的关键字，然后再分别对这两部分记录继续进行快速排序，从而使整个序列有序。
一趟快速排序的过程称为一次划分，具体做法是:附设两个位置指示变量i和j，它们的初值分别指向序列的第一个记录和最后一个记录。设枢轴记录(通常是第一个记录)的关键字为pivot,则首先从j所指位置起向前搜索,找到第一个关键字小于 pivot 的记录时将该记录向前移到i指示的位置，然后从i所指位置起向后搜索，找到第一个关键字大于 pivot 的记录时将该记录向后移到j所指位置，重复该过程直至i与j相等为止。

4.8归并排序

归并排序是一种分治的排序算法。它的基本思想是将待排序的数据序列不断地分成更小的部分，直到每个部分只有一个元素为止（此时每个部分都是有序的），然后再以一定的方式合并这些部分，使得它们最终成为一个有序的整体。