数组

数组类型	存储地址计算
一维数组a[n]	a[i]的存储地址为：a + i * len
二维数组a[m][n]	a[i][j]的存储地址（按行存储）：a + (i * n + j) * len a[i][j]的存储地址（按列存储）：a + (j * m + i) * len

稀疏矩阵

一个矩阵中存储的大量元素是0

稀疏矩阵	示意图	要点
上三角矩阵		在矩阵中下标分别为 i 和 j 的元素，对应的一维数组的下标计算公式为：$(2n-i+1) \times i \div 2 + j$
下三角矩阵		在矩阵中下标分别为 i 和 j 的元素，对应的一维数组的下标计算公式为：$(i+1) \times i \div 2 + j$

考试中常用代入法：

数据结构的定义

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，是一种数据组织、管理和存储的格式。

逻辑结构：线性结构、非线性结构（树、图）

线性表

线性结构的基本表现，分顺序存储结构（顺序表）和链式存储结构（链表）

顺序存储与链式存储对比：

队列与栈

元素按照a、b、c的次序进入栈，写出所有可能的出栈序列：

• a进，a出，b进，b出，c进，c出，顺序：a，b，c
• a进，b进，b出，a出，c进，c出，顺序：b，a，c
• a进，b进，c进，c出，b出，a出，顺序：c，b，a
• a进，a出，b进，c进，c出，b出，顺序：a，c，b
• a进，b进，b出，c进，c出，a出，顺序：b，c，a

广义表

广义表是由n个表元素组成的有限序列，是线性表的推广

通常用递归的形式进行定义，记作：$LS=(a_{0}, a_{1}, ...,a_{n})$

LS是表名，$a_{i}$是表元素，可以是表（称作子表），也可以是数据元素（称作原子），n是广义表的长度（最外层包含的元素个数）

n=0的广义表为空表，递归定义的重数是广义表的深度，简单来说就是定义中所含括号的重数（原子的深度为0，空表的深度为1），也就是嵌套层数

基本运算：取表头head(Ls)和取表尾tail(Ls)，

若有：LS1=(a, (b, c), (d, e))，则 head(LS1) = a，tail(LS1) = ((b, c), (d, e))

树与二叉树

基本概念

• 结点的度：结点拥有的孩子数
• 树的度：所有结点中最高的度
• 叶子结点：没有孩子结点的结点
• 分支结点：有分支的结点
• 内部结点：不是根节点和叶子结点
• 父结点、子结点、兄弟结点
• 层次

二叉树

几种特殊的二叉树：

二叉树的重要特性：

二叉树的遍历

层次遍历

按层进行遍历：1，2，3，4，5，6，7，8

前序遍历

先访问根结点，再访问左子树结点，再访问右子树结点：1，2，4，5，7，8，3，6

中序遍历

先访问左子树结点，再访问根结点，再访问右子树结点：4，2，7，8，5，1，3，6

后序遍历

先访问左子树结点，再访问右子树结点，再访问根结点：4，8，7，5，2，6，3，1

反向构造二叉树

知道一定的二叉树的遍历序列，反向推出二叉树的情况

树转二叉树

基本原则：

• 孩子结点→左子树结点（只取最左边的作为左子树结点）
• 兄弟结点→右子树结点
• 可以用连线法简化转换流程

查找二叉树（二叉排序树）

一类比较特殊的二叉树

• 左孩子小于根
• 右孩子大于根

插入结点：

1. 若该键值结点已存在，则不再插入
2. 若查找二叉树为空树，则以新结点为查找二叉树
3. 将要插入结点键值与插入后父结点键值比较，就能确定新结点是父结点的左子结点还是右子结点

删除结点：

1. 若待删除结点是叶子结点，则直接删除
2. 若待删除结点只有一个子结点，则将这个子结点与待删除结点的父结点直接连接
3. 若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s，结点s必属于以上两种情况之一

最优二叉树（哈夫曼树）

用于哈夫曼编码，让原始信息的编码长度变得更短，属于无损压缩

• 树的路径长度
• 权：结点的值
• 带权路径长度：权*路径长度
• 树的带权路径长度（树的代价）：所有叶子结点带权路径长度的累加

构造一个哈夫曼树要达到的效果是树的带权路径长度最短

线索二叉树

目的：将空闲的结点分支利用起来，方便遍历，左子树结点指向对应遍历顺序的前序结点，右子树结点指向对应遍历顺序的后序结点

平衡二叉树

平衡度：左子树深度-右子树深度，所有叶子结点的平衡度都是0

图

基本概念

• 有向图：边有方向
• 无向图：边没有方向
• 完全图：无向图每对顶点间都有一条边相连，有向图每对顶点间都有两条有向边相互连接

图的存储

邻接矩阵

用一个n阶方阵R来存放图中各结点的关联信息

对于无向图，邻接矩阵为了节省存储空间，可以只存上三角或下三角

邻接表

首先把每个顶点的邻接顶点用链表示出来，然后用一个一维数组来顺序存储上面每个链表的头指针

图的遍历

深度优先遍历DFS

1. 首先访问出发顶点V
2. 依次从V出发搜索V的任意一个邻接点W
3. 若W未访问过，则从该点出发继续深度优先遍历

类似于树的前序遍历

V1，V2，V4，V8，V5，V3，V6，V7

广度优先遍历BFS

1. 首先访问出发顶点V
2. 然后访问与顶点V邻接的全部未访问顶点W、X、Y...
3. 然后再依次访问W、X、Y...邻接的未访问顶点

V1，V2，V3，V4，V5，V6，V7，V8

拓扑排序

用一个序列来表达一个图中哪些序列可以先执行，哪些序列可以后执行

把有向边表示活动之间开始的先后关系，这种有向图称为用顶点表示活动网络，简称AOV网络

图的最小生成树

把图中的边只留下若干条权值最小的，能够把所有顶点连接起来，成为一棵树

普利姆算法

基本思想：从任意一个结点出发，将其定为红点集，其它为蓝点集，选出一条从红点集到蓝点集最短距离的边，并将连接到的点纳入红点集，重复进行

克鲁斯卡尔算法

首先确定选几条边，然后从最短的边开始选起，但不能选边之后成环

算法基础

算法的特性

• 有穷性：执行有穷步后结束
• 确定性：算法中每一条指令都必须有确切的含义，不能含糊不清
• 输入：≥0
• 输出：≥1
• 有效性：算法的每个步骤都能有效执行并能得到确定的结果

算法的复杂度

时间复杂度：程序运行从开始到结束所需要的时间

空间复杂度：一个算法在运行过程中临时占用存储空间大小的度量

一般来说，算法中原操作重复执行的次数是规模n的某个函数$T(n)$，由于许多情况下要精确计算$T(n)$是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间

如果存在两个常数$c$和$m$，对于所有的$n$，当$n \geq m$时有$f(n) \leq cg(n)$，则有$f(n) = O(g(n))$。也就是说，随着$n$的增大，$f(n)$渐进地不大于$g(n)$。例如，一个程序的实际执行时间为$T(n) = 3n^3+2n^2+n$，则$T(n)=O(n^3)$

常见的对算法执行所需时间的度量：

$O(log_2n)$多用于树中

查找

顺序查找

从头到尾进行比较，若存在则成功

查找成功时，顺序查找的平均查找长度为（等概率情况下）：

时间复杂度为$O(n)$

二分查找

前提：序列是有序的

mid为小数是向下取整

二分查找在查找成功时关键字的比较次数最多为$\lfloor log_2n \rfloor + 1$次

二分查找的时间复杂度为$O(log_2n)$

散列表

基本思想：已知关键字集合U，最大关键字为m，设计一个函数Hash，它以关键字为自变量，关键字的存储地址为因变量，将关键字映射到一个有限的、地址连续的区间T[0..n-1]（n<<m）中，这个区间就称为散列表，散列查找中使用的转换函数称为散列函数

散列表冲突的解决方法：线性探测法、伪随机数法

排序

稳定排序：相同的元素在排序后的相对位置不变

内排序：在内存中的排序

直接插入排序

当插入第i个记录时，R1，R2，...，Ri-1已经排好序，因此Ri与他们进行比较，找到合适的位置插入，速度很慢

希尔排序

希尔（Shell）排序：先取一个小于n的整数$d_1$作为第一个增量，把文件的全部记录分成$d_1$个组。所有距离为$d_1$的倍数的记录放在同一个组中。先在各组内进行直接插入排序，然后去第二个增量$d_2 < d_1$重复上述的分组和排序，直至所取的增量$d_t=1(d_t<d_{t-1}<O<d_2<d_1)$，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法，比直接插入排序快

直接选择排序

首先在所有记录中选出最小的记录，把它与第1个记录交换，接下来从剩下的纪录中选出最小的与第2个记录交换，以此类推

堆排序

所有排序算法中最复杂的算法

堆：

先将序列建立堆，然后输出堆顶元素，再将剩余元素建立堆，输出堆顶元素

初建堆的过程：从最后一个非叶子结点开始调整，与其子结点比较大小

排序过程：

效率比直接选择排序高，应用场景在取前n个排序后元素

冒泡排序

通过相邻元素之间的比较和交换，将排序码较小的元素逐渐从底部移到顶部

快速排序

采用分治法，基本思想是将原问题分解成若干个规模更小但结构与原问题相似的子问题，递归地解决子问题

1. 在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录都分成两组，第一组都小于该数，第二组都大于该数
2. 采用相同的方法对左右两组分别进行排序，直到所有记录都排到相应的位置为止

归并排序

把两个或两个以上有序子表合并成一个新的有序表

若只合并两个，称为二路合并

合并过程：比较A[i]和A[j]的排序码大小，若A[i]的排序码小于等于A[j]的排序码，则将第一个有序表中的元素A[i]复制到R[k]中，并令i和k分别加1，如此循环下去，知道其中一个有序表比较和复制完，然后再将另一个有序表的剩余元素复制到R中

基数排序

借助多关键字排序思想对但逻辑关键字进行排序的方法。适合于元素很多而关键字较少的序列

基数的选择和关键字的分解是根据关键字的类型来决定的，例如关键字是十进制数，则按个位、十位、百位来分解

排序算法的比较（重要）