考研数据结构笔记

绪论

数据结构的基本概念

基本概念和术语

数据：
  是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合

数据元素：
  一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位

数据对象：
  是具有相同性质的数据元素的集合，是数据的一个子集

数据类型：
  是一个值的集合和定义在此集合上的一组操作的总称

抽象数据类型（ADT）：
  描述了数据的逻辑结构和抽象运算，通常用（数据对象，数据关系，基本操作集）这样的三元组表示，从而构成一个完整的数据结构

数据结构：
  是相互之间存在一种或多种特定关系的元素的集合，包括：逻辑结构、存储结构和数据运算

数据结构三要素

逻辑结构：
  是指数据元素之间的逻辑关系，与数据的存储无关，是独立于计算机的分类：集合、线性结构、树形结构、图状结构

存储结构：
  是用计算机语言实现的逻辑结构，它依赖于计算机语言。

  分类：

1. 顺序存储：
   • 优点是可以实现随机存取，每个元素占用最少的存储空间；
   • 缺点是只能使用相邻的一块存储单元，因此可能产生较多的外部碎片。
2. 链式存储：
   • 优点是不会出现碎片现象，能充分利用所有存储单元；
   • 缺点是每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取。
3. 索引存储：
   • 优点是检索速度快；
   • 缺点是增加附加的索引表后会占用较多的存储空间。另外，在增加和删除数据时要修改索引表，因而会花费较多的时间。
4. 散列存储：
   • 优点是检索、增加和删除结点的操作都很快；
   • 缺点是若散列函数不好，则可能出现元素存储单元冲突，而解决冲突会增加时间和空间开销。

运算：
  定义是针对逻辑结构的，指出运算的功能；实现是针对存储结构的，指出运算的具体操作步骤

总结

1. 循环队列是用顺序表表示的队列，是一种数据结构。
2. 栈示一种抽象数据类型，可采用顺序存储或链式存储，只表示逻辑结构
3. 线性表、栈和队列的逻辑结构都是相同的，都属于线性结构，只是他们对数据的运算不同从而表现出不同的特点

算法和算法评价

算法的基本概念

算法：
  是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每一条指令都表示一个或多个操作

算法的特性：

1. 有穷性：一个算法（对任何合法的输入值）必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2. 确定性：对于相同的输入只能得出相同的输出。
3. 可行性：算法中所有描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
4. 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
5. 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

算法的设计目标：
  正确性、可读性、健壮性、效率与低存储需求

算法效率的度量

时间复杂度

  频度：
  指该语句在算法中被重复执行的次数

  算法的时间复杂度不仅依赖于问题的规模 $n$ ，也取决于输入数据的性质

空间复杂度
  算法原地工作是指算法所需的辅助空间为常量，即 $O(1)$ 。

总结

1. 同一个算法，实现语言的级别越高，执行效率越低
2. 在已经确定时间复杂度的情况下比较算法，不用再考虑特殊输入值

线性表

线性表的定义和基本操作

线性表的定义

  线性表是具有相同数据类型的 $n(n\ge 0)$ 个数据元素的有限序列，当 $n=0$ 时该线性表是一个空表。

  注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念。

线性表的顺序表示

顺序表的定义

  线性表的顺序表示又称顺序表。
  顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。
  注意：线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的。

  顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间 $O(1)$ 内找到制定的元素。
  顺序表的存储密度高，每个结点只存储数据元素。
  顺序表逻辑上相邻的元素物理上也相邻。

顺序表上操作的实现

  线性表插入算法的平均时间复杂度为 $O(n)$ 。
  线性表删除算法的平均时间复杂度为 $O(n)$ 。
  线性表查找算法的平均时间复杂度为 $O(n)$ 。

线性表的链式表示

单链表的定义

  线性表的链式存储又称单链表。
  单链表是非随机存取的存储结构。

  头结点的数据域可以不设任何信息，也可以记录表长等相关信息。

头结点和头指针的区分：
  不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。

引入头结点的优势：

1. 在链表的第一个位置上操作和在表其他位置上的操作一致，无需进行特殊处理。
2. 空表和非空表的处理也就得到了统一。

单链表上基本操作的实现

对一结点进行前插操作
  当要将结点 *s 插入结点 *p 的前面时，可以先将 *s 插入结点 *p 的后面，然后交换 p->date 和 s->data ，这样既满足了逻辑关系，又能使插入操作的时间复杂度为 $O(1)$ 。

删除结点*p
  将其后继结点的值赋予其自身，然后删除后继结点，也能使的时间复杂度为 $O(1)$ 。

循环链表

循环单链表
  循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。

  有时，对单链表常做的操作是在表头和表尾进行的，此时对循环单链表不设头指针而仅设尾指针，从而使的操作效率更高。

顺序表和链表的比较

空间分配
  基于存储的考虑…链式存储结构存储密度是小于1的。

总结

1. 插入删除元素后要记得修改线性表长度。
2. 顺序表为随机存取的存储结构，链表为非随机存取。

栈和队列

栈

栈的基本概念

栈的定义
  栈——只允许在一端进行插入或删除操作的线性表。
  空栈——不含任何元素的空表。

总结

1. $n$ 个不同元素进栈，出栈序列的个数（卡兰特数）： $\frac{1}{n+1}C_{2n}^n$

队列

队列的基本概念

队列的定义
  队列——也是一种操作受限的线性表。

队列常见的的基本操作
  不可以随便读取队列中间的某个数据。

队列的顺序存储结构

循环队列
  队列长度：(Q.rear+MaxSize-Q.front)%MaxSize

特殊矩阵的压缩存储

矩阵的压缩存储

  压缩存储：指多个值相同的元素之分配一个存储空间，对零元素不分配存储空间。
  特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有对称矩阵、上（下）三角矩阵、对角矩阵等。

对称矩阵
  元素下标之间对应关系如下：

$$k= \begin{cases} \frac{i(i-1)}{2}+j-1 , & i\ge j (下三角区和主对角线元素) \\\\ \frac{j(j-1)}{2}+i-1 , & i < j (上三角区元素a_{ij}=a{ji}) \end{cases}$$

三角矩阵
  下三角矩阵元素下标之间对应关系：

$$k= \begin{cases} \frac{i(i-1)}{2}+j-1 , & i\ge j (下三角区和主对角线元素) \\\\ \frac{n(n+1)}{2} , & i < j (上三角区元素) \end{cases}$$

  上三角矩阵元素下标之间对应关系：

$$k= \begin{cases} \frac{(i-1)(2n-i+2)}{2}+(j-i) , & i\le j (上三角区和主对角线元素) \\\\ \frac{n(n+1)}{2} , & i > j (下三角区元素) \end{cases}$$

三对角矩阵
  矩阵中3条对角线上的元素 $a_{i,j}(1\le i,j\le n,|i-j|\le 1)$ 在一维数组中存放的下标为 $k=2i+j-3$ 。
  反之，若已知三对角矩阵中某元素 $a_{i,j}$ 存放于一位数组的第 $k$ 个位置，则可得 $i=\lfloor (k+1)/3+1\rfloor,j=k-2i+3$

稀疏矩阵

  稀疏矩阵压缩存储后便失去了随机存取特性。

树与二叉树

树的基本概念

树的定义

  任意一颗非空树应满足：有且仅有一个特定的称为根的结点

  树的定义是递归的，是一种递归的数据结构。树作为一种逻辑结构,同时也是一种分层结构，具有以下两个特点：

1. 树的根结点没有前驱结点，除根结点外的所有结点有且仅有一个前驱结点。
2. 树中所有节点可以有零个或多个后继结点。

  n个结点的树中有n-1条边。

树的基本术语

1. 根是树中唯一没有双亲的结点
2. 树中结点最大的度数称为树的度
3. 结点的深度是从根结点开始自顶向下逐层累加的；树的高度是从叶结点开始自底向上逐层累加的；树的高度是树中结点的最大层数
4. 树中结点的子树从左到右是有次序的，不能交换，这样的树称为有序树，有序树中，一个结点的子结点按从左到右的顺序出现是有关联的，反之则称为无序树
5. 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所有经过的边的个数

树的性质

1. 树中的结点数等于所有结点的度数加1
2. 度为 $m$ 的树中第 $i$ 层上至多有 $m^{i-1}$ 个结点 $(i\ge 1)$
3. 高度为 $h$ 的 $m$叉树至多有 $(m^h-1)/(m-1)$ 个结点
4. 具有 $n$ 个结点的 $m$ 叉树的最小高度为 $\lceil \log_m (n(m-1)+1) \rceil$

二叉树的概念

二叉树的定义及其主要特征

二叉树的定义
  二叉树的子树有左右之分，其次序不能任意颠倒
  二叉树是有序树，即使树中结点只有一颗子树，也要区分它是左子树还是右子树

  二叉树与度为2的有序树的区别

1. 度为2的树至少有3个结点，而二叉树可以为空
2. 度为2的有序树的孩子结点的左右次序是相对另一个孩子结点而言的，而二叉树无论其孩子数是否为2，都要区分左右次序

几种特殊的二叉树
  满二叉树
  一颗高度为 $h$ ，且含有 $2^h-1$ 个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点。
  满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2 。

  双亲结点：$\lfloor i/2 \rfloor$
  左孩子结点：$2i$
  右孩子结点：$2i+1$

  完全二叉树

1. 若 $i\le \lfloor n/2 \rfloor$ ，则结点 $i$ 为分支结点，否则为叶子结点。
2. 叶子结点只能在层次最大的两层上出现。
3. 若有度为1的结点，则只能有一个，且该结点只有左孩子而无右孩子（重要特征）。
4. 按层序编号后，一旦出现某个结点（编号为 $i$ ）为叶子结点或只有左孩子，则编号大于 $i$ 的结点均为叶子结点。
5. 若 $n$ 为奇数，则每个分支结点都有左子女和右子女；若 $n$ 为偶数，则编号最大的分支结点（编号为 $n/2$），只有左子女，没有右子女，其余分支结点左、右子女都有。

  二叉排序树
  空二叉树或者是：左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字。左子树和右子树又各是一棵二叉排序树。

  平衡二叉树
  树上任一结点的左子树和右子树的深度之差不超过1 。

二叉树的性质

1. 非空二叉树上的叶子结点数等于度为2的结点数加1，即 $n_0=n_2+1$
2. 非空二叉树上第 $k$ 层上至多有 $2^{k-1}$ 个结点 $(k\ge 1)$ 。
3. 高度为 $h$ 第二叉树至多有 $2^h-1$ 个结点 $(h\ge 1)$ 。
4. 完全二叉树按从上到下、从左到右的顺序依次编号 $1,2,\dots ,n$ ,则有以下关系：
   1. 当 $i>1$ 时，结点 $i$ 的双亲结点编号为 $\lfloor i/2 \rfloor$ ,即当 $i$ 为偶数时，其双亲结点的编号为 $i/2$ ，他是双亲结点的左孩子；当 $i$ 为奇数时，其双亲结点的编号为 $(i-1)/2$ ，他是双亲结点的右孩子。
   2. 当 $2i\le n$ 时，结点 $i$ 的左孩子编号为 $2i$ ，否则无左孩子。
   3. 当 $2i+1\le n$ 时，结点 $i$ 的右孩子编号为 $2i+1$ ，否则无右孩子。
   4. 结点 $i$ 所在层次（深度）为 $\lfloor \log_2 i \rfloor +1$ 。
5. 具有 $n$ 个 $(n>0)$ 结点的完全二叉树的高度为 $\lceil \log_2(n+1) \rceil$ 或 $\lfloor \log_2 n \rfloor +1$ 。

二叉树的存储结构

链式存储结构
  在含有 $n$ 个结点的二叉链表中，含有 $n+1$ 个空链域（重要结论，经常出现在选择题中）

总结

1. 完全二叉树中度为1 的结点树为0或1
2. 完全二叉树：$n=n_0+n_1+n_2=2n_0-1+n_1 \quad n_1=(n+1)\%2$
3. 完全三叉树：有 $n$ 个结点的完全三叉树的高度为 $\lceil \log_3 (2n+1) \rceil$
4. 完全二叉树若有n个结点，则最后一个分支结点编号为 $i=\lfloor n/2 \rfloor$ , 则叶子结点数为 $n-i$

二叉树的遍历和线索二叉树

二叉树的遍历

由遍历序列构造二叉树
  若只知道二叉树的先序序列和后序序列，则无法唯一确定一颗二叉树。

线索二叉树

总结

1. 后续线索二叉树无法找到后继结点的原因时他可能有右孩子
2. 线索二叉树是物理结构
3. 含有 $n$ 个结点的线索二叉树含有的线索数为 $2n-1$

树、森林

树、森林与二叉树的转换

  可以用同一存储结构的不同解释将一棵树转换为二叉树。
  二叉树转换为树或森林是唯一的。

总结

1. 森林转换为二叉树以后空指针域个数为原先非叶结点树 +1

树与二叉树的应用

二叉排序树

二叉排序树的查找效率分析
  若二叉排序树的左、右子树的高度之差的绝对值不超过1，则这样的二叉排序树称为平衡二叉树。它的平均查找长度达到 $O(\log_2 n)$ 。

  相同的关键字其插入顺序不同可能生成不同的二叉排序树

平衡二叉树

平衡二叉树的定义
  保证任意结点的左、右子树的高度之差的绝对值不超过1，则这样的二叉排序树称为平衡二叉树。
  左子树与右子树的高度差为该结点的平衡因子，其值只可能是 $-1,0,1$ 。

平衡二叉树的插入
  LR 和 RL 旋转时，新结点究竟是插入左子树还是插入右子树不影响旋转过程。

总结

1. 高度为 $h$ 的平衡二叉树最少结点数递推公式： $n_0=0,n_1=1,n_2=2,n_h=1+n_{n-1}+n_{n-2}$

哈夫曼树和哈夫曼编码

哈夫曼树的定义
  从树根结点到任意结点的路径长度（经过的边数）与该结点上权值的乘积称为该结点的带权路径长度。树中所有结点的带权路径长度之和称为该树的带权路径长度。
  带权路径长度最小的二叉树称为哈夫曼树，也称最优二叉树。

哈夫曼编码
  若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。

总结

1. $n_2=n_0-1$
2. 哈夫曼树只有叶子结点和度为2的结点

图

图的基本概念

图的定义

  线性表可以是空表，树可以是空树，但图不可以是空图。就是说，图中不能一个顶点也没有，图的顶点集 $V$ 一定非空，但边集 $E$ 可以为空此时图中只有顶点而没有边。

简单图

1. 不存在重复边
2. 不存在顶点到自身的边

多重图
  若 $G$ 中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联。

  多重图的定义和简单图是相对的。

完全图（也称简单完全图）
  在无向图中，若任意两个顶点之间都存在边，则称该图为无向完全图。
  含有 $n$ 个顶点的无向完全图有 $n(n-1)/2$ 条边。

  在有向图中，若任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。
  含有 $n$ 个顶点的有向完全图有 $n(n-1)$ 条有向边。

子图
  若满足 $V(G’)=V(G)$ 的子图 $G’$ ，则称其为 $G$ 的生成子图。

连通、联通图和联通分量
  若图 $G$ 中任意两个顶点都是连通的，则称图 $G$ 为连通图。

  若一个图有 $n$ 个顶点，并且边数小于 $n-1$ ，则此图必是非连通图。

强连通图、强连通分量
  在有向图中，从顶点 $v$ 到顶点 $w$ 和从顶点 $w$ 到顶点 $v$ 之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。

  强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性，在有向图中考虑强连通性。

顶点的度、入度和出度
  无向图的全部顶点的度的和等于边数的两倍。

  有向图的全部顶点的入度之和与出度之和相等，并且等于边数。

路径、路径长度和回路
若一个图有 $n$ 个顶点，并且有大于 $n-1$ 条边，则此图一定有环。

总结

1. 连通分量是无向图的极大连通子图，其中极大的含意是将依附于连通分量中顶点的所有边都加上，所以连通分量中可能存在回路，不一定是生成树。

图的存储及基本操作

邻接矩阵法

  设图 $G$ 的邻接矩阵为 $A$ ， $A^n$ 的元素 $A^n[i][j]$ 等于由顶点 $i$ 到顶点 $j$ 的长度为 $n$ 的路径的数目。

邻接表法

  第 $i$ 个单链表中的结点表示依附于顶点 $v_i$ 的边（ 对于有向图则是以顶点 $v_i$ 为尾的弧）。

总结

1. 顶点 $v$ 对应的边表存放的以顶点 $v$ 为起点的边所对应的另一个顶点 $u$

图的遍历

深度搜索优先

  对于同样一个图，基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。

总结

1. 利用深度优先搜索可以判断图中是否有环。

图的应用

最小生成树

  一个连通图的生成树是图的极小连通子图，它包含图中的所有顶点，并且只含尽可能少的边。

Prim算法
  Prim算法的时间复杂度为 $O(|V|^2)$ ，不依赖于 $|E|$ ，因此它适用于求解稠密的图的最小生成树。

Kruskal算法
  时间复杂度为 $O(|E|\log |E|)$ 。因此，Kruskal算法 适合于边稀疏而顶点较多的图。

最短路径

Dijkstra算法求单源最短路径问题
  时间复杂度：$O(|V|^2)$

  要找出所有结点对之间的最短距离，需要对每个结点运行一次Dijkstra算法，即时间复杂度为 $O(|V|^3)$

  边上带有负权值时，Dijkstra算法并不适用。

Floyd 算法求各顶点之间最短路径问题
  时间复杂度：$O(|V|^3)$

  Floyd算法允许图中带有负权值的边，但不允许有包含带负权值的边组成回路。Floyd算法同样适用于带权无向图。

拓扑排序

  有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图。

  AOV网：顶点表示活动的网络，记为AOV网。
  任何活动 $V_1$ 不能以他自己作为自己的前驱或后继。

拓扑排序
  时间复杂度为 $O(|V|+|E|)$
  对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之则不一定成立。

总结

1. 拓扑排序序列唯一的图不一定是线性的（王道P228-14题）。
2. 一个有向图中含有顶点数大于1的强连通分量，意味着该有向图存在环，无法进行拓扑排序。
3. 若一个有向图的邻接矩阵为三角矩阵（对角线上元素为0），则图中必不存在环，拓扑序列必然存在。

关键路径

  AOE网：用边表示活动的网络，简称为AOE网。
  在AOE网中仅有一个入度为0的点，称为开始顶点（源点），也仅存在一个出度为0的点，称为结束顶点（汇点）。

  具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

事件 $v_k$ 的最早发生时间 $v_e(k)$
  在计算 $v_e(k)$ 时，是按从前往后的顺序来计算的。

事件 $v_k$ 的最迟发生时间 $v_1(k)$
  在计算 $v_1(j)$ 时，是按从后往前的顺序来计算的。

一个活动 $a_i$ 的最迟开始时间 $l(i)$ 和其最早开始时间 $e(i)$ 的差额 $d(i)=l(i)-e(i)$
  称 $l(i)-e(i)=0$ 即 $l(i)=e(i)$ 的活动 $a_i$ 是关键活动。

总结

1. 缩短所有关键路径上共有的任意一个关键活动的持续时间可缩短关键路径长度。

下载本文PDF