《数据结构导论》考试重点

第一章概论

数据结构是计算机组织数据和存储数据的方式。
数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的一组操作。
1976年瑞士计算机科学家尼克劳斯·维尔特（Niklaus Wirth）曾提出一个著名的公式：算法 + 数据结构 = 程序。
数据由若干个数据元素组成，数据元素由若干个数据项组成。

逻辑结构、存储结构、运算

数据的逻辑结构是指数据元素之间的逻辑关系。逻辑关系是指数据元素之间的关联方式或邻接关系。
四类基本的逻辑结构：集合、线性结构、树形结构、图结构。
集合结点之间没有邻接关系；线性结构结点之间一对一的关系；树形结构结点之间一对多的关系；图结构结点之间多对多的关系。
与数据元素本身的形式、内容、相对位置、个数无关的是数据的逻辑结构。
数据的逻辑结构在计算机中的实现称为数据的存储结构（或物理结构）。
存储结构一般有四种形式：顺序存储、链式存储、索引存储、散列存储。
运算是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。这种加工以数据的逻辑结构为对象。
运算的实现是指该运算的算法；算法指的是求解给定问题所需的处理步骤及其执行顺序。

时间复杂度、空间复杂度

算法时间复杂度指的是算法在给定输入下的计算量。
算法的空间复杂度指的是算法中除了输入数据占用的存储空间之外所需的附加存储空间的大小，即所需的存储量。
在估算算法空间复杂度时，一般只需要分析辅助变量所占用的空间。
常数阶 $O(1)$，对数阶 $O(log_{2}n)$，线性阶 $O(n)$，线性对数阶 $O(nlog_{2}n)$，多项式阶有：平方阶 $O(n^2)$、立方阶 $O(n^3)$、K次方阶 $O(n^k)$，指数阶 $O(2^n)$。

第二章线性表

顺序表

顺序表插入新元素，需要移动元素的个数为 $n-i+1$（i为下标从1开始就需要+1，否则不需要）。
顺序表删除元素，需要移动元素的个数为 $n-i$（i为下标，从1开始）。
顺序表插入算法的平均移动次数约为 $\frac{n}{2}$，算法时间复杂度为 $O(n)$。
顺序表删除算法的平均移动次数约为 $\frac{n-1}{2}$（下标从0开始），算法时间复杂度为 $O(n)$。
单链表和双向循环链表插入操作顺序不可以颠倒。
双向循环链表删除操作顺序可以颠倒。
用顺序存储实现的线性表称为顺序表，一般使用数组来表示。

链表

在单链表中，指针p所指的结点为最后一个结点的条件是p->next == NULL。

第三章栈、队列和数组

栈和队列可看作是特殊的线性表，运算受限的线性表。
函数的嵌套调用和程序递归的处理都是用栈来实现的。操作系统中进程调度、网络管理中的打印服务等都是用队列来实现的。
术语：
- 进栈：指插入运算。出栈：指删除运算。栈顶：允许进栈和出栈的一端。栈底：栈顶的另一端。
- 空栈：不含任何数据元素的栈。栈顶元素：处于栈顶位置的数据元素。
- 上溢：栈的容量已经满了，此时再进行进栈就会发生上溢。下溢：空栈做出栈就会产生下溢，因为栈中没有任何数据元素。

栈、双栈的运算

顺序栈使用数组实现，栈顶top默认为下标0，判断栈空的核心stack->top == 0，判断栈满的核心stack->top == maxSize -1，进栈操作的核心stack->top++; stack->data[stack->top] = x;，出栈操作的核心stack->top--;。
双栈判断上溢的条件为：$top+1=top2$。

队列的基本概念

栈是后进先出（Last In First Out），队列是先进先出（First In First out）。
入队列：在队列尾部进行插入运算；出队列：在队列首部进行删除运算。
链队列是一个带有头结点的单链表组成，队列首部的指针指向头结点，头指针指向首结点，队列尾部的指针指向尾结点，队列空的时候，队列首部和尾部的指针均指向头结点。

队列、循环队列的运算

顺序队列入队列操作的核心SQ.rear = SQ.rear + 1; SQ.data[SQ.rear] = x;，出队列操作的核心SQ.front = SQ.front + 1。
循环队列解决了假溢出问题，队首和队尾都指向下标0的位置，少使用一个元素空间以解决无法区分空和满的情况。
循环队列入队列操作的核心CQ.rear = (CQ.rear + 1) % maxSize; CQ.data[CQ.rear] = x;，出队列操作的核心CQ.front = (CQ.front + 1) % maxSize;，队列满的条件(CQ.rear + 1) % maxSize == CQ.front;，队列空的条件CQ.rear == CQ.front;。

数组、矩阵

计算数组元素的存储地址公式 $(n * i + j) \times k$，其中m是行数量，n是列数量，i是在m行的下标，j是在n列的下标，k是每个元素占用的存储大小。
可将 $n^2$ 个元素压缩存储到含有 $\frac{n(n + 1)}{2}$ 个元素的一维数组中。
假设m行n列的矩阵有t个非零元素，当$t«m*n$时，则称矩阵为稀疏矩阵；三元组表示法：((i, j, v), (i, j, v), ...)，其中i是行，j是列，v是非零元素的值。

第四章树和二叉树

术语：
- 结点的度：某一个结点有多少个直接孩子。树的度：结点的度的最大值，也就是所有结点里直接孩子最多的那个。
- 结点的层次：把一棵树比作一个层级金字塔，从根结点为1，每下一层+1，数到结点所在的层级。树的高度/深度：结点的层次的最大值，也就是树一共有多少层。

二叉树的基本概念

一棵树的结点个数最少为0；二叉树第 i（i≥1）层上至多有 $2^{i-1}$ 个结点；深度为 k（k≥1）的二叉树至多有 $2^{k}-1$ 个结点。
对任何一棵二叉树，若度数为0的结点个数为$n_0$，度数为2的结点个数为$n_2$，则 $n_0=n_2+1$。
含有n个结点的完全二叉树的深度为 $⌊log_2n⌋+1$。
对于完全二叉树，根结点为1对结点进行编号，$i>1$ 时（i是指被编号的那个结点），结点双亲的编号为 $⌊\frac{i}{2}⌋$。
二叉树不是完全二叉树，满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
二叉树的先序遍历次序为根左右，中序遍历次序为左根右，后序遍历次序为左右根，层次遍历次序为每层从左往右。

存储结构

具有n个结点的二叉树（链表结构）中，有 $2n$ 个指针域，其中只有 $n-1$ 个用来指向结点的左、右孩子，其余的 $n + 1$ 个指针域为NULL。
树的存储结构分别有：孩子链表表示法、孩子兄弟链表表示法、双亲表示法。孩子兄弟链表的结构形式与二叉链表完全相同。

树和二叉树

树转换成二叉树：
1. 加线，所有兄弟结点之间加一条线，彼此连接起来。
2. 抹线，除了结点的第一个左孩子，其他孩子与结点的连线全部抹掉。
3. 旋转，以根节点为轴心，对树进行顺时针的适当旋转。
森林转换成二叉树：
1. 将森林中的每棵树转换成二叉树。
2. 加线，转换以后的二叉树，从第二棵二叉树开始，将其根节点作为前一棵二叉树根结点的右子树，以此类推。
二叉树转换成森林：
1. 抹线，断开根结点与右孩子的连线，此时得到两棵二叉树。
2. 抹线再加线，二叉树根节点的左子树的右子树们均断开连接，改成均与根节点之间连接，如果根节点有右子树，重复步骤1的操作。
3. 剩下的二叉树重复按以上步骤进行处理。

判断树和哈夫曼树

一棵判定树描述了一种分类方法；用于描述分类过程的二叉树称为判定树。
有n个叶子结点的哈夫曼树，其结点的总数为 $2n-1$。

第五章图

术语：
- 顶点：即图中的圆圈。边：即图中圆圈之间的连线，也称为顶点的偶对。权：即连线旁边的数值，也称为边的权。
- 带权图：每条边都带有权的图。有向图：顶点的偶对是有序的。无向图：顶点的偶对是无序的。
- 弧：有向图的边又称为弧。弧头：表示弧的终点，即弧有箭头的一端。弧尾：表示弧的始点/起点。
- 有向完全图：任何两个顶点之间都有弧的有向图。无向完全图：任何两个顶点之间都有边的无向图。
- 顶点的度：与该顶点相关联的边的数目。
- 入度：把以顶点v为终点的弧的数目称为v的入度，记为ID(v)。
- 出度：把以顶点v为始点的弧的数目称为v的出度，记为OD(v)。
- 路径：从一个顶点x到另一个顶点y之间的路线。路径长度：路径上边/弧的数目。
- 简单路径：序列中顶点不重复出现的路径。回路：第一个顶点和最后一个顶点相同的路径，也称为环。简单回路：除了第一个顶点和最后一个顶点外，其余顶点不重复的回路。
- 连通：顶点x到顶点y有路径，则称顶点x和顶点y是连通的。
- 连通图：图中任意两个顶点都是连通的。连通分量：无向图中的极大（最大）连通子图。
- 强连通相关术语含义与连通一样，只是强连通用于描述有向图，不做赘述。
有序偶对用尖括号<>括起来，无序偶对用圆括号()括起来。
无向图中一个顶点的度是指图中与该顶点相邻接的顶点数。
一个具有n个顶点的有向完全图的弧的数量为：$P_{n}^{2}=n(n-1)$；一个具有n个顶点的无向完全图的边的数量为：$C_{n}^{2}=\frac{n(n-1)}{2}$。

存储结构

邻接表是顺序存储与链式存储相结合的存储方法。
无向图的邻接矩阵是一个对称矩阵，有向图的邻接矩阵是一个稀疏矩阵。
在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为$n^{2}-2e$；而有向图的邻接矩阵中，零元素个数为$n^{2}-e$。

遍历

图的遍历方法有两种：深度优先搜索DFS、广度优先搜索BFS。
图的遍历操作类似于树的遍历操作；深度搜索的顶点的访问序列不是唯一的。
深度优先搜索类似于树的先序遍历；广度优先搜索类似于树的层次遍历。
以邻接表为存储结构，深度优先搜索算法的时间复杂度是$O(n+e)$，其中n为图的顶点数，e为图的边数。
以邻接矩阵作为存储结构，深度优先搜索算法的时间复杂度是$O(n^2)$，其中n为图的顶点数。

应用

一个图的最小生成树是图所有生成树中权总和最小的生成树；最小生成树有两种算法：普里姆Prim算法、克鲁斯卡尔Kruskal算法。
克鲁斯卡尔Kruskal方法的思想，初始时将每个顶点看成一个单独的连通分量，找所有连通分量之间的权值最小的一条边，将该边添加到两个连通分量中，并合并成一个新的单独的连通分量，重复这个过程，直到所有顶点最终形成一个连通分量。
最短路径算法可以采用迪杰斯特拉Dijkstra算法，思想是按照最短路径长度递增的方法产生从一点到其他顶点的最短路径。
完成拓扑排序的前提条件是AOV网中不允许出现回路。
以邻接表作为存储结构，拓扑排序算法的时间复杂度为$O(n+e)$，n是图的顶点个数，e是图的弧的数目。

第六章查找

对于一种数据结构，查找表的逻辑结构是集合。
顺序表为(b1, b2, b3)，查找b1，b2，b3的概率分别为0.2、0.2、0.6，则顺序查找法的平均查找长度为$(0.2\times3)+(0.2\times2)+(0.6\times1)=1.6$。

顺序表

向一个长度为n的顺序表中第i($1{\leq}i{\leq}n$)个元素之前插入一个元素时，需向后移动$n-i+1$个元素。
从一个长度为n的顺序表中删除第i个元素($1{\leq}i{\leq}n$)时，需向前移动$n-i$个元素。
在长度为n的带有岗哨的顺序表中，进行顺序查找，查找不成功时，与关键字比较次数为$n+1$。
采用顺序查找方法查找长度为n的顺序表时，平均查找长度为$\frac{(n+1)}{2}$。

二叉排序树

中序遍历一棵二叉排序树可得到一个键值的升序序列。
二叉排序树的平均查找长度介于 $O(n)$ 和 $O(log_2n)$ 之间。

散列表、散列法、解决冲突方法

散列法：数字分析法、除留取余法、平方取中法、基数转换法。
除留取余法$H(key)=key{\quad}mod{\quad}p(p{\leq}n)$，p通常选小于散列表长度n的素数，如果p是偶数，得到的散列值总是偶数，如果是奇数则总是奇数。
解决冲突方法：线性探测法、二次探测法、链地址法、多重散列法、公共溢出区法。
非同义词之间对同一个散列地址的争夺现象称为堆积。
线性探测法容易产生堆积。二次探测法缺点不容易探测到整个散列表的所有空间。
链地址法实际上也可能存在堆积，退化成链表（书上未提及，仅个人观点）。
多重散列法优点不容易产生堆积，缺点计算量大。
公共溢出区法，在发生冲突的情况下，将同义词存入溢出表，基本表就不可能发生堆积（书上原话）。
要完全避免散列所产生的“堆积”现象，通常采用链地址法解决冲突（书中课后题的答案，按书中教的来）。
用线性探测法解决冲突，可能要探测多个散列地址，这些位置上的键值不一定都是同义词。

第七章排序

稳定性是排序方法本身的特性，与数据无关。
当待排序序列已基本有序时，插入排序和交换排序比较有效（性能高）。当待排记录数量较大时，选择排序比较有效（性能高）。

插入排序

插入排序方法有直接插入排序、折半插入排序、表插入排序、希尔排序。
直接插入排序类似图书馆整理图书的过程，时间复杂度为$O(n^2)$，空间复杂度为$O(1)$，是稳定的，不适宜n较大的序列。

交换排序

交换排序方法有冒泡排序、快速排序。
冒泡排序时间复杂度为$O(n^2)$，空间复杂度$O(1)$，是稳定的。
快速排序实质上是对冒泡排序的一种改进。快速排序时间复杂度为$O(nlog_2n)$，最坏情况下时间复杂度近似$O(n^2)$，空间复杂度取决于实现的算法，是不稳定的，对数量n较小算法效果不明显，数量较大效果明显。

选择排序

选择排序方法有直接选择排序、堆排序。
直接选择排序时间复杂度为$O(n^2)$，空间复杂度$O(1)$，是不稳定的，不适宜n较大的序列。
堆排序平均和最坏情况下时间复杂度都是$O(nlog_2n)$，空间复杂度为$O(1)$，是不稳定的，不适宜待排序记录较少时使用，记录数很多效果明显。

归并排序

归并排序方法有有序序列的合并、二路归并排序。
有序序列的合并算法时间复杂度为$O(n-h+1)$。
二路归并排序时间复杂度为$O(nlog_2n)$，空间复杂度$O(n)$，是稳定的。

目录

第一章 概论

第二章 线性表

第三章 栈、队列和数组

第四章 树和二叉树

第五章 图

第六章 查找

第七章 排序

第一章概论

第二章线性表

第三章栈、队列和数组

第四章树和二叉树

第五章图

第六章查找

第七章排序