《王道数据结构考研复习指导》笔记

Published: November 01, 2020 by Authur Lee

Categories:
Data_Structure 44

本博客主要是将一些不易注意到的知识点、易错点以及易忘点整理一下，更多的是用来补充学习而非系统学习。

框架结构

《王道数据结构考研复习指导》此书针对的是考计算机专业的，所以考试范围比较小。主要是八部分内容，如下。

绪论
线性表
栈和队列
串
树与二叉树
图
查找
排序

一、绪论

【主要内容】基本概念、时空复杂度

数据：信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合；
数据元素：数据的基本单位，通常作为一个整体来考虑，由若干个数据项组成；
数据项：构成数据元素的不可分割的最小单位；
数据对象：具有相同性质的数据元素的集合，是数据的一个子集;
数据类型：一个值的集合和定义在此集合上的一组操作的总称，分为原子类型、结构类型、抽象数据类型；
数据结构：相互之间存在一种或多种特定关系的数据元素的集合，数据元素相互之间的关系称为结构；
- 数据结构三要素：逻辑结构、存储结构、数据的运算；
- 逻辑结构
  - 数据元素之间的逻辑关系；
  - 与数据的存储无关，独立于计算机；
  - 分为线性结构和非线性结构
  - 四种逻辑结构：集合、线形结构、树形结构、图状结构(网状结构)；
- 存储结构
  - 也叫物理结构；
  - 数据在计算机中的表示(又称“映像”)；
  - 包括数据元素的表示和关系的表示；
  - 是用计算机语言实现的逻辑结构，故而依赖于计算机语言；
  - 分类：顺序存储、链式存储、索引存储、散列存储；
    - 顺序存储
      - 优：随机存储，每个元素占用最小的存储空间；
      - 缺：只能用相邻的一整块存储单元，产生较多的外部碎片；
    - 链式存储
      - 优：不会出现碎片现象，可充分利用所有存储单元；
      - 缺：每个元素因存储指针而占用额外空间，而且只能顺序存取；
    - 索引存储
      - 优：检索速度块；
      - 缺：
        
        附加的索引表额外占用存储空间；
        
        增加和删除数据时也要修改索引表，因而会花费较多时间；
    - 散列存储
      - 优：检索、增加、删除结点的操作都很快；
      - 缺：如果散列函数不好，则可能会出现元素存储单元的冲突，而解决冲突会增加时间和空间开销；
- 数据的元素
  - 运算的定义是针对逻辑结构，指出运算的功能；
  - 运算的实现是针对存储结构的，指出运算的具体操作步骤；
算法的五个特性：有穷性、确定性、可行性、输入、输出；
“好”的算法要达到的要求：正确性、可读性、健壮性、效率与的存储量需求；

时间复杂度的运算规则：

$operation1$

$operation2$

常见的时间复杂度：

$comparison$

算法的空间复杂度：若输入数据所占空间值取决于问题本身，和算法无关，则只需分析输入和程序之外的额外空间。
算法原地工作：算法所需的辅助空间为常量，即O(1)。

二、线性表

【线性表的特点】

表中元素的个数有限；
表中元素具有逻辑上的顺序性，表中元素由其先后次序；
表中元素都是数据元素，每个元素都是单个元素；
表中元素的数据类型都相同，这意味着占有相同大小的存储空间；

顺序表

【顺序表的特点】表中元素的逻辑顺序与其物理顺序相同；

称i为元素ai在线性表中的位序。

线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的。

一维数组可以静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据将会产生溢出，进而导致程序崩溃。而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储空间的目的，而不需要为线性表一次性地划分所有空间。

动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时决定。

顺序表特点：随机访问；存储密度高；插入和删除操作需要移动大量元素。

链式表

插入和删除操作都不需要移动元素，而只需修改指针。

利用单链表就可以解决顺序表大量存储单元的缺点，但单链表附加指针，也存在浪费存储空间的缺点。由于单链表的元素离散地分散在存储空间中，所以单链表是非随机存取的存储结构。

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

【引入头结点的优点】链表的第一个位置上的操作和在表地其他位置上的操作一致，无须进行特殊处理；无论链表是否为空，其头指针都指向头结点的非空指针(空表中头结点的指针域为空)。

【对某一结点进行前插操作】

一般方法：找到插入结点的前驱结点，然后后插；
骚方法：仍然插到插入结点的后面，然后交换两结点内的数据；

删除结点的操作也可以通过交换数据的方式 —— 先存储待删除结点后继结点的信息，然后删除后继结点，再把存储下来的信息复制到本该删除的结点上。

【求表长】单链表的长度是不包括头结点。

静态链表

静态链表里面的指针是结点的相对地址（数组下标），又称游标。

静态链表以next == 1作为其结束的标志。

三、栈和队列

栈

n个不同元素进栈，出栈元素不同排列的个数为 $Catalan数$ 。该公式称为卡特兰(Catalan)数，可用数学归纳法证明。

因为栈只能在顶端操作，所以对栈的定义中，栈底指针是不必要的。

顺序栈的入栈操作受数组上界的约束，当对栈的最大空间使用不足时，有可能发生栈上溢，此时应该向即时向用户报告消息，以便及时处理，避免出错，

【共享栈】利用栈底位置不变的特性，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

共享栈目的：是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被栈满时才上溢。其存取数据的时间复杂度均为O(1).

【链栈】便于多个栈共享存储空间和提高其效率，且不存在栈上溢的情况；通常使用单链表表示，并规定所有操作都是在单链表的表头进行。

队列

循环队列中，区分循环队列是满还是空，有三种处理方法：

牺牲一个单元来区分队空和对满，入队时少用一个队列单元；
类型中增设表示元素个数的数据成员；
类型增设tag数据成员，以区分是队满还是队空。

如果填空题问的是两种方法，那么选1、3两点。

加入程序中要使用多个队列，与多个栈的情形一样，最好使用链式队列，这样就不会出现存储分配不合理和溢出的问题。

若限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变成两个栈底相邻的栈。

队列在计算机系统中的应用：

解决主机与外部设备之间速度不匹配的问题；
解决由多用户引起的资源竞争问题。

特殊矩阵的压缩存储

每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围为数组的维界。

数组是线性表的推广。一维数组可视为一个线性表，二维数组可视为其元素也是定长线性表的线性表，以此类推。数组一旦被定义，其维数和维界就不再改变。

除了结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。

三角矩阵与对角矩阵的不同：存储完下三角和主对角线上的元素之后，紧接着存储对角线上方的常量一次(就算是0也要存储)。如此就可将下三角矩阵A[1..n][1..n]压缩存储在B[n(n+1)/2+1]中。

稀疏矩阵的三元组即可以采用数组存储，也可以采用十字链表法存储。

四、串

串的存储结构：

定长顺序存储表示
堆分配存储表示
块链存储表示

模式匹配算法：主串i指针无序回溯，并继续从该位置开始进行比较。

next[j]的含义：在子串第j个字符与主串发生失配时，则跳到子串的next[j]位置重新与主串当前位置进行比较。

五、树与二叉树

树适合于表示具有层次结构的数据.

结点的深度是从根结点开始自顶向下逐层增加；结点的高度从叶结点开始自底向上逐层增加。

度为m的树中第i层上至多有 $m^{i-1}$ 个结点；
高度为h的m叉树至多有 $num$ 个结点；
具有n个结点的m叉树最小高度为 $height$ 。

二叉树的子树有左右之分，次序不能任意颠倒。

二叉树是有序树，即使树中结点只有一棵子树，也要区分它是左子树还是右子树。

平衡二叉树是二叉排序树。

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映结点之间的逻辑关系。这样子既能最大可能地节省空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

顺序存储二叉树时最好从数组下标1开始存储。

因为顺序存储的空间率比较低，所以二叉树一般都采用链式存储结构。

【二叉树的遍历】指按某条搜索路径访问树中的某个结点，使得每个结点均被访问一次，而且仅被访问一次。

常见的遍历：先序(NLR)、中序(LNR)、后序(LRN)

【后序非递归遍历算法的思路分析】从根结点开始，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，但是此时不能进出栈并访问，因为如果其有右子树，还需按相同的规则对其右子树进行处理。直至上述操作进行不下去，若栈顶元素想要出栈并被访问，要么右子树为空，要么右子树刚被访问完(此时左子树早已被访问完)，这样就保证了正确的访问顺序。

【可以唯一确定一棵二叉树的三组遍历序列】

中序、先序
中序、后序
中序、层序

【关于线索二叉树的规定】若无左子树，令其lchild指向其前驱结点；若无右子树，令rchild指向其后继结点；还需增加两个标志域标识指针域是指向左(右)孩子还是指向前驱(后继)。

加上线索的二叉树称为线索二叉树，其中指向结点前驱和后继的指针称为线索。

在后序线索二叉树中找结点的后继较为复杂，可分为三种情况：

若结点x是二叉树的根，则其后继为空；
若结点x是其双亲的右孩子，或其双亲的左孩子且其双亲没有右子树，则其后继即为双亲；
若结点x是其双亲的左孩子，且其双亲有右子树，则其后继即为双亲的右子树上按后序遍历列出的第一个结点。

【树的存储结构】

双亲表示法(用一组连续空间来存储每个结点)
孩子表示法(将每个结点的孩子结点都用单链表链接起来形成一个线形结构，此时n个结点就有n个孩子链表，叶子结点的单链表为空表)
孩子兄弟表示法(也叫二叉树表示法)

孩子兄弟表示法比较灵活，其最大的优点为可以方便地实现树转换为二叉树的操作，易于查找结点的孩子；但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个parent域指向其父结点，则查找父结点也很方便。

树的应用：并查集。通常用树(森林)的双亲表示作为并查集的存储结构，每个子集合以一棵树表示。通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲结点为负数。

六、图

【图的存储】

邻接矩阵法
邻接表法
十字链表
邻接多重表

【图的遍历】从图的某一顶点出发，按照某种搜索方法沿着图中的所有顶点访问一次且一次。

【BFS遍历图的时间复杂度】采用邻接表存储方式时，算法总的时间复杂度为O(|V|+|E|)；采用邻接矩阵存储方式时，算法总的时间复杂度为O(|V|^2)。

【DFS遍历图的时间复杂度】采用邻接表存储方式时，算法总的时间复杂度为O(|V|+|E|)；采用邻接矩阵表示时，总的时间复杂度为O(|V|^2)。

构造最小生成树有多种算法，但大多数算法都利用了最小生成树的如下性质：假设G=(V,E)是一个带权连通无向图，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u属于U，v属于V-U，则必存在一棵包含边(u,v)的最小生成树。

由于AOV网中各顶点的地位平等，每个编号是人为的。对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之不一定成立。

七、查找

【查找表】用于查找的数据集称为查找表。

【关键字】数据元素中唯一标识该元素的某个数据项的值。

【算法程序中的哨兵作用】引入哨兵可以避免很多不必要的判断语句，从而提高程序效率。

理想情况下，对散列表进行查找的时间复杂度为O(1)。

八、排序

对于不稳定的排序算法，只需举出一组关键字的实例，说明它的不稳定性即可。

时间复杂度一般是由比较和移动次数决定的。

一趟快速排序是一个交替搜索和交换的过程。

快速排序是所有内部排序算法中平均性能最优的排序算法。

快速排序中，并不产生有序子序列，但每趟排序后会将枢轴(基准)元素放到最终的位置上。