前言

数据结构作为六七年前甚至小学就有接触过的知识，如今再次与其狭路相逢。不同于之前所有数据结构知识的学习，考研的数据结构会明显偏向于理论知识而非实践应用，故特此另开一篇用以记录学习历程。

【20210924】虽然基本上是按照王道的复习指导来复习的，但实际专业科目并非 408，所以目录和 408 是有出入的，但大体而言的知识点覆盖是一致的。随着 2022 年 408 考纲的修订，会有如下知识点不会提及：串、并查集、平衡树、红黑树、外部排序等。

目录

第一章 绪论

第二章 线性表

第三章 数组

第四章 栈和队列

串

第七章 树与二叉树

第八章 图

第九章 文件及查找

第十章 内排序

数据结构考研笔记

第一章 绪论

1.1 数据结构的基本概念

1.1.1 基本概念和术语

数据是信息的载体；

数据元素是数据的基本单位，由若干个数据项（最小单位）组成；

数据对象是具有相同性质的数据元素的集合；

数据类型分为原子类型、结构类型、抽象数据类型；

数据结构是存在某种关系的数据元素的集合，包括逻辑结构、存储结构与数据的运算。

1.1.2 数据结构三要素

① 逻辑结构

逻辑结构指数据元素之间存在的逻辑关系，是固有的客观联系；

逻辑结构分为线性结构与非线性结构，比如：线性表、树、图等；

② 存储结构

存储结构又称为物理结构，指数据结构在计算机中的表示（映像），是计算机内部的存储方法；

存储结构主要有顺序存储、链式存储、索引存储和散列存储；

一种逻辑结构通过映像便可以得到它的存储结构；

诸如顺序表、哈希表、链表这样的表述，它们既体现了逻辑结构（均为线性），又体现了存储结构（顺序、散列、链式）；

而这样的表述我们往往就直接称之为数据结构；

诸如有序表，它只体现了逻辑结构（线性），而存储结构是未知的（可以是顺序、链式……）；

不存在只体现存储结构而不体现逻辑结构的表述；

所以，我们认为：逻辑结构独立于存储结构。

③ 数据的运算（算法）

算法包括运算的定义（取决于逻辑结构，体现算法功能）与实现（取决于存储结构，体现于操作步骤）。

1.2 算法的基本概念

算法的 5 个重要特性：有穷性、确定性、有效性（可行性）、输入与输出；

一个好的算法的目标：正确性、可读性、鲁棒性、效率与低存储量需求。

1.3 算法分析

时间复杂度指算法所有语句被重复执行次数总和的数量级。

常见时间复杂度比较：

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

(log 表示以 2 为底的对数)

空间复杂度指算法耗费存储空间的数量级。

1.4 题目与总结

本章不在 408 考纲范围内，但时间复杂度的计算却是考试重点。选择题几乎没什么难度，但如果出在应用题上，推导过程的书写却是个问题，总结如下：

① 循环条件包含主体变量，将执行次数 t 代入该条件再计算，如：

> Pop(&S, &x) 出栈，弹出栈顶元素 x 并返回

> GetTop(S, &x) 读栈顶元素 x 并返回

> DestroyStack(&S) 销毁栈，释放空间

4.2 堆栈的顺序存储结构

顺序栈的实现：略

顺序栈的基本运算：略

共享栈：两个顺序栈共享一个一维数组，栈底分别设在两端，栈顶向中间延伸。

4.3 堆栈的链式存储结构

采用链式存储的栈称为链栈。

优点：便于多个栈共享存储空间，提高效率，且不存在栈溢出的情况。

链栈没有头结点，直接指向栈顶元素。

4.4 队列的基本概念

队列是一种只允许在表的一端插入，另一端删除的线性表。

队列的操作：

> InitQueue(&Q) 初始化空队列 Q

> QueueEmpty(Q) 判断队列是否为空

> EnQueue(&Q, x) 入队

> DeQueue(&Q, &x) 出队，删除队头元素 x 并返回

> GetHead(Q, &x) 读队头元素 x 并返回

4.5 队列的顺序存储结构

队列的顺序存储：略

循环队列：普通队列会出现假溢出情况，故引用循环队列，将队列从逻辑上视为一个环，利用取余运算实现。

由于循环队列在队空与队满的判断条件是等价的，故需要一些处理方式来区分：

> 牺牲一个单元来区分，约定“队头在队尾下一位置作为队满的标志”；

> 增设表示元素个数的数据成员。

循环队列的操作：略

4.6 队列的链式存储结构

队列的链式存储：采用链式存储的队列称为链队列。

链队列往往设计成带头结点的单链表。

链式队列的基本操作：略

双端队列

双端队列指两端都可以入队出队操作的队列，两端称为前端和后端。

栈和队列的应用

栈在括号匹配中的应用 

略

栈在表达式求值中的应用

后缀表达式可以轻松获得运算符关系，且不用处理括号。用栈处理。

栈在递归中的应用

可以用栈来模拟递归过程，以消除递归。

对于同一个问题，非递归算法效率通常比递归算法更高。

队列在层次遍历中的应用

比如 BFS。

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

比如页面替换算法。

4.7 题目与总结

【王道 3.2 选择第 8 题】【2011 408真题】循环队列存储在数组 A[0..n-1] 中，队列非空时 front 和 rear 分别指向队头与队尾。初始时队列为空，且第一个进入队列的元素存储在 A[0]，则 front 和 rear 的初值为？

反向思考。首先插入后的队首与队尾指向的位置均为 0，且插入元素只会更改 rear 的值，则 front 在插入前仍为 0，而 rear 需要 -1，对于循环队列，0 的前一个位置为 n - 1。故答案分别为 0, n - 1。

【王道 3.3 选择第 11 题】【2012 408真题】将中缀表达式 a+b-a*((c+d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+ 时，用栈存放暂时不能确定运算次序的操作符，转换过程中栈的操作符个数最大为？

看了下解析，实在是太麻烦了点吧。不过自己做的时候没想太多，前后两道题也做对了。

无括号时正常乘除在先加减在后。有括号时，遇到右括号，完成对应的左括号之后范围内所有运算。

比如本题，+ 直接运算，可弹出；- 不动，因为后面是个 *；加上第一个 (；遇到第一个 ) 时，第二个 ( 及里面的 + 弹出；遇到第二个 ) 时，第一个 ( 及里面的 / 与 - 弹出；* 运算完成，- * 先后弹出；+ 直接运算，弹出。

整个过程中，操作符最大的时刻在：- * ( / -，即遇到第二个 ) 之前。 

串

串的定义和实现

串的定义

串是由零个或多个字符组成的有限序列，为字符串的简称。

串的存储结构

串有三种存储方式：

> 定长顺序存储表示：分配一个固定长度

> 堆分配存储表示：按串长动态分配，使用指针指向串的起始地址

> 块链存储表示：类似于线性表链式存储结构，具体实现时可以使每个结点存放一个或多个字符

串的基本操作

> StrAssign(&T, chars) 将串 T 赋值为 chars

> StrCopy(&T, S) 将串 S 复制得到串 T

> StrEmpty(S) 判断串 S 是否为空

> StrCompare(S, T) 比较串 S 与 T 的大小（S > T 返回值 > 0；= / =；< / StrLength(S) 返回串 S 的长度

> SubString(&Sub, S, pos, len) 返回串 S 的第 pos 个字符起长度为 len 的子串 Sub

> Concat(&T, S1, S2) 返回串 S1 和串 S2 连接而成的串 T

> Index(S, T) 返回主串 S 中与串 T 相同的子串第一次出现的位置（不存在则为 0 ）

> ClearString(&S) 清空串 S

> DestroyString(&S) 销毁串 S，释放空间

串的模式匹配

简单的模式匹配算法

子串的定位操作通常称为串的模式匹配，求的是子串（模式串）在主串中的位置。

具体算法略。

改进的模式匹配算法 —— KMP 算法

部分匹配值：字符串的最长公共前后缀长度；

比如字符串 'ababa'，其部分匹配值为 3，对应的前缀与后缀为 'aba'；

在算法竞赛中，通常我们会将模式串的所有前缀的部分匹配值后移一位再依次存入一个数组，一般称为 fail 数组或 next 数组；第一位填充 -1；

还是 'ababa'，其 fail 数组为：[-1, 0, 0, 1, 2]；

对于算法竞赛上 KMP 算法使用的更详细介绍，可以移步 [知识点]KMP算法，尽管在知识点大全的填坑计划中被遗弃，但其实内容在去年刚刚更新，时效性与正确性应该不会有太大欠缺。

而对于考研或者其他相关的笔试，更强调的是算法思想而非实现过程，所以在学习时可以用不同的思路。

求得 fail 数组后，每次匹配失败，则将模式串当前指针前移到 fail[匹配失败的位置]，主串指针不动，同时再次对齐两个指针。这样思考更适用于笔试考场。

注意题目可能给出的 fail 数组所有值 +1，以适应首位序号不为 0 而为 1 的标号方式。

KMP 算法的进一步优化

优化构建 fail 数组的过程。假设模式串为 a，且匹配失败恰好发生在第 i 位，则下次匹配必然是与第 fail[i] 位，但如果 a[i] = a[fail[i]]，则必然再次匹配失败，以此类推。所以为了避免多余的匹配，我们将这种情况下的 fail[i] = j 优化为 fail[i] = fail[j]，相当于再递归一次。

优化后的数组一般命名为 nextval 数组。

第七章 树与二叉树

7.1 树的基本概念

7.1.1 树的定义

树是 n 个结点的有限集。对于任意一棵空树，满足：

① 有且仅有一个特定的根结点；

② n > 1 时，除去根结点外的其他结点又可分为若干个互不相交的子树。

7.1.2 树逻辑上的特点

略

7.1.3 树的逻辑表示方法

文氏图表示法；凹入表示法；嵌套括号（广义表）表示法；树形表示法。

【可能需要补充】

7.1.4 基本名词术语

> 祖先 / 子孙 / 双亲（父） / 孩子（子） / 兄弟

> 度：结点的子结点个数为结点的度；最大结点的度为树的度

> 分支结点 / 叶子结点

> 深度（自顶向下） / 高度（自底向上） / 层次

> 有序树 / 无序树

> 路径 / 路径长度

> 森林：m 棵互不相交的树集合，加上一个共同根结点后即可认为是一棵树

7.1.5 树的性质

① 树的结点数 = 所有结点度数之和 + 1；

② 度为 m 的树第 i 层至多 m^(i-1) 个结点；

③ 高度为 h 的 m 叉树至多 (m^h - 1) / (m - 1) 个结点；

④ 具有 n 个结点的 m 叉树最小高度为 log_m[n(m-1) + 1] 向上取整。

7.2 树的存储结构

7.2.1 多重链表结构

将每个结点的子结点用单链表