期末数据结构复习大纲

按考点

一、 算法设计核心：线性结构 (分值占比 20%)

这一部分要求能够书写代码，重点在于对指针操作和逻辑结构的理解。

• 线性表 (Linear List)
  • 顺序表：随机存取特性，插入和删除需移动元素，平均时间复杂度为 $O(n)$。
  • **链表 (Linked List)**：顺序存取特性，插入和删除无需移动元素，只需修改指针。例如：单链表，双链表，循环链表…
    • 双链表——相比单链表可以向前索引，例如从后往前打印双链表就更容易实现
    • 循环链表，尾指针指向头指针。最适合处理满足以下两个特征的数据结构：周期性（Periodicity）：业务逻辑是循环往复的，没有终点。对等性（Equality）：在环中，没有绝对的“老大”（Head）和“老幺”（Tail），每个节点在逻辑上地位平等。例如约瑟夫问题。
  • 核心操作：初始化、取值、查找、插入（s->next = p->next; p->next = s;）和删除（p->next = q->next; delete q;）
  • 2.6 顺序表和链表的比较
    顺序表| 单链表
    |查找 |O(1)| O(n)|
    |插入 |移动元素O(n)| 查找位置O(n)|
    |删除 |移动元素O(n) |查找位置O(n)
    |适用范围| 频繁查找|频繁插入和删除|
  • 线性表的其他存储方法：
    • 静态链表
      • 使用数组元素的下标来模拟单链表的指针
• 栈 (Stack)
  • 特性：后进先出 (LIFO)。
  • 实现：顺序栈（注意栈顶指针 top 和栈底指针 base）和链栈。
    • 顺序栈本质：顺序表的简化。唯一需要确定的是数组的哪一端表示栈顶，哪一端表示栈底
      • 实现：栈–>分配一整块内存的数组，注意：上溢：栈满时入栈； 下溢：栈空时出栈
      • 特例：共享栈：多个栈共享同一个空间； 也要注意上溢和下溢的问题；
    • 链栈
      • 栈顶：单链表的头部最容易操作，栈顶设在头部
      • 不需要头结点
    • 两者比较：
      • 时间耗费：O(1)
      • 空间耗费：顺序栈的预分配，导致空间浪费
  • 应用
    • 设计算法，把十进制数转换为二进制输出，eg. 77 = 1001101
    • 字符串正序输入，倒序输出？

n 链栈的指针域，有额外开销
* 应用：数制转换、括号匹配、表达式求值及递归实现。

• 队列 (Queue)
  • 特性：先进先出 (FIFO)。
  • 循环队列（顺序存储结构）：解决“假溢出”问题。关键公式：队空条件 front == rear；队满条件 (rear+1)%MAXSIZE == front。front队头指向第一个元素的前一个位置，这个位置不能回存储任何一个元素，所以实际上能存储的数据为MAXSIZE-1
  • 链队：注意出队时最后一个元素的特殊处理（需修改尾指针指向头结点）。
  • 应用：一般银行排队机、路由器数据转发队列等都是优先级队列，即同时有多个队列，每个队列优先级不同，请根据自己所学设计一个优先级队列的结构。

• 串：eg. 字符串，每个节点是一个字符；是0个或多个字符组成的有限序列；
  • 存储结构：顺序结构 or 链式结构
  • 空格串－－“ ”长度为1；空串－－“”长度为0；
  • 子串—-串中任意连续的字符组成的子序列。
  • 常用的三种顺序存储结构：
    • ![[Pasted image 20251225201422.png]]
    • 压缩形式和非压缩形式
    • ![[Pasted image 20251225201446.png]]
  • kmp算法：本次字符串匹配不成功时，下次不用回到i-j+1的位置进行匹配。即不回溯算法
  • 模式匹配：粗暴解法：回溯到i-j+1;
• 基于栈的经典算法
  • 函数调用：进栈； 函数返回：出； 递归终止 == 栈空
  • 例如：汉诺塔、斐波那契、二分搜索、归并排序、迷宫问题……
• 多维数组：类型相同的数据结构构成的有序集合，元素受n个线性关系的约束；通常只有存取和修改操作
  • 顺序存储结构，但是内存是一维的，要把多维的数组映射成一维的，如二维的有行优先和列优先两种
• 其他一些算法问题：递归调用、dp……
• 稀疏矩阵
  • 两种表示方法：三元组、十字链表

二、 算法应用重点：非线性结构与图论 (分值占比 60%)

这一部分侧重于逻辑应用和手工推演（如画图、写序列），无需背诵复杂代码。

• 树与二叉树 (Tree & Binary Tree)
  • 应用：编译系统中，表示源程序的语法结构；2，数据库组织信息；3，计算机系统中的XML，JSON数据，磁盘路径结构，DOM树等等… 压缩：Huffman
  • 树与二叉树关系：逻辑关系，存储关系
  • 性质：第 $i$ 层至多有 $2^{i-1}$ 个结点；深度为 $k$ 的二叉树至多有 $2^k-1$ 个结点；叶子结点数 $n_0 = n_2 + 1$。
  • 遍历 (Traversal)：先序、中序、后序（递归定义）以及层序遍历。
  • 存储：二叉链表（lchild, data, rchild）。
  • **哈夫曼树 (Huffman Tree)**：带权路径长度 (WPL) 最短的树；构造方法（每次选两个权值最小的）；哈夫曼编码（左0右1，前缀编码）。
• 图 (Graph)
  • 图的表示
    • （v1,v2）代表v1和v2之间有一条边
    • <v1,v2> 代表v1到v2之间有一条弧
  • 存储结构：
    • 邻接矩阵：以点找树，适合存储稠密图，空间复杂度 $O(n^2)$。
    • 邻接表：以边找树，适合存储稀疏图，空间复杂度 $O(n+e)$。
    • 十字链表
    • 邻接多重表
  • 遍历：深度优先搜索 (DFS，类似先序) 和广度优先搜索 (BFS，类似层序，需用队列)。
  • **最小生成树 (MST)**：
    • 普里姆 (Prim) 算法：归并点，适合稠密图。
    • 克鲁斯卡尔 (Kruskal) 算法：归并边，适合稀疏图。
  • 最短路径
    • 迪杰斯特拉(Dijkstra)
    • 弗洛伊德（floyd）：邻接矩阵起手，遍历所有节点更新距离矩阵（D）和路径矩阵（P，记录终点的前一个节点）；
  • 最小生成树和最短路径：两个解决的问题不一样, 最短路径是求最短的路线, 最小生成树是解决怎么花最小的成本连通所有点

三、 查找与排序：算法分析 (分值占比 60%)

要求掌握各类算法的过程（每一趟的状态）及其性能指标。

• 查找 (Searching)
  • 顺序查找：设置“监视哨”可免去检查下标越界。
  • 折半查找 (Binary Search)：仅适用于有序的顺序表；平均查找长度约为 $\log_2(n+1)-1$。
  • **散列表 (Hash Table)**：散列函数（除留余数法）、冲突处理（开放地址法如线性探测、链地址法）、装填因子 $\alpha$。
• 排序 (Sorting)
  • 插入类：直接插入排序、希尔排序（缩小增量排序）。
  • 交换类：冒泡排序（相邻比较）、快速排序（划分枢轴，平均性能最好 $O(n\log_2n)$）。
  • 选择类：简单选择排序、堆排序（大根堆/小根堆，适合 $n$ 较大时）。
  • 性能对比：熟记各排序算法的时间/空间复杂度和稳定性（见教材表 8.2）。

四、 基础理论：单选题考点 (分值占比 20%)

• 基本概念：数据、数据元素、数据项、逻辑结构（集合、线性、树、图）、存储结构（顺序、链式）。
• 算法评价：正确性、可读性、健壮性、高效性；时间复杂度和空间复杂度的计算（大 $O$ 记号）。

---

按章节

根据提供的教材大纲与讲义内容，以下是按章节顺序排列的数据结构知识清单：

第 1 章 绪论

• 基本概念：数据、数据对象、数据元素（数据的基本单位）、数据项（数据的最小单位）。
  • 数据的逻辑表示&存储方法–数据结构
  • 数据处理–算法
• 逻辑结构：集合、线性、树、图（网状）结构。
• 存储结构：顺序存储（借助相对位置）和链式存储（借助指针）。
• **抽象数据类型 (ADT)**：由用户定义的数学模型及在其上的一组操作。
• 算法评价：
  • 特性：有穷性、确定性、可行性、输入、输出。
  • 度量：时间复杂度（大 $O$ 记号，如 $O(1), O(n), O(n^2), O(\log_2n)$）和空间复杂度。
  • ==循环层数不一定完全与复杂度成正比，要具体判断==
  • 构成一个算法的5要素：输入，输出，有穷性，确定性，可行性
  • 描述算法：自然语言，流程图，程序设计语言，伪代码

第 2 章 线性表

• 定义：相同类型数据元素的有限序列。
• **顺序表 (SqList)**：
  • 特点：随机存取；逻辑相邻，物理位置也相邻。
  • 操作：插入和删除时需移动大量元素，平均移动次数约为 $n/2$ 或 $(n-1)/2$，时间复杂度为 $O(n)$。
• **链表 (LinkList)**：
  • 形态：单链表（带头结点或仅带头指针）、循环链表、双向链表、静态链表。
  • 操作：插入和删除不需移动元素，只需修改指针（如 s->next = p->next; p->next = s;），时间复杂度为 $O(n)$。
  • 单链表：缺点1：空链表、非空链表的处理不同；n 缺点2：插入、删除首结点的处理和其他结点不同
  • 1 如何同时快速找到头尾结点？- 循环链表2 如何可以同时搜索前驱和后继结点？- 双链表3 没有指针的语言，如何实现链表？- 静态链表
• 应用：有序表的合并（时间复杂度 $O(m+n)$）。

第 3 章 栈和队列

• **栈 (Stack)**：
  • 特性：**后进先出 (LIFO)**。
  • 操作：入栈 (Push)、出栈 (Pop)，仅在栈顶进行。
  • 递归：利用系统递归工作栈保存活动记录，涉及分治和回溯思想。
• **队列 (Queue)**：
  • 特性：**先进先出 (FIFO)**。
  • 循环队列：解决“假溢出”问题。关键公式：队空 $front == rear$；**队满 $(rear+1)%MAXSIZE == front$**；长度计算 $(rear-f+QueueSize)%QueueSize$。
  • 链队：带头结点的链式存储，需注意最后一个元素出队时的尾指针处理。

第 4 章 串、数组和广义表

• **串 (String)**：由零个或多个字符组成的有限序列。
  • 模式匹配：BF 算法（带回溯，$O(n \times m)$）和 KMP 算法（无回溯，$O(n+m)$，需计算 $next$ 和 $nextval$ 数组）。
• **数组 (Array)**：
  • 存储映象：行序为主序（C++ 默认）或列序为主序。
  • 特殊矩阵压缩：对称矩阵、三角矩阵（压缩至一维数组）和稀疏矩阵（利用三元组或十字链表存储）。
• 广义表：线性表的推广，元素可以是原子或子表。操作有取表头 (GetHead) 和取表尾 (GetTail)。

第 5 章 树和二叉树

• 二叉树性质：
  • 第 $i$ 层至多有 $2^{i-1}$ 个结点；深度为 $k$ 的二叉树至多有 $2^k-1$ 个结点。
  • **叶子结点数 $n_0 = n_2 + 1$**。
• 遍历：先序、中序、后序（递归实现）以及层序遍历（利用队列辅助）。
• 树和森林：存储结构包括双亲表示法、孩子表示法、孩子兄弟表示法；掌握树、森林与二叉树的相互转换。
• **哈夫曼树 (Huffman Tree)**：带权路径长度 (WPL) 最短的树；构造方法（每次选两棵权值最小的树）及哈夫曼编码（前缀编码）。
• **并查集 (Union-Find)**：处理不相交集合的合并与查找，涉及等价类划分。

第 6 章 图 (Graph)

• 存储结构：邻接矩阵（适合稠密图）和邻接表（适合稀疏图）。
• 图的遍历：深度优先搜索 (DFS，类似先序) 和广度优先搜索 (BFS，类似层序，需用队列)。
• 最小生成树 (MST)：普里姆 (Prim) 算法（归并点，适合稠密图）和克鲁斯卡尔 (Kruskal) 算法（归并边，适合稀疏图）。
• 最短路径：迪杰斯特拉 (Dijkstra) 算法（单源最短路径）和弗洛伊德 (Floyd) 算法。
• 拓扑排序与关键路径：AOV-网进行拓扑排序判定环；AOE-网通过 $ve, vl$ 计算找关键活动及关键路径。

第 7 章 查找 (Searching)

• 线性表查找：顺序查找（设置“监视哨”）、折半查找（仅限有序顺序表，$O(\log_2n)$）、分块查找。
• 树表查找：**二叉排序树 (BST)（左小右大）、平衡二叉树 (AVL)**（四种平衡旋转调整）、B-树/B+ 树。
• 散列表 (Hash Table)：构造方法（除留余数法）；冲突处理（开放地址法如线性探测、链地址法）；查找效率取决于**装填因子 $\alpha$**。

第 8 章 排序 (Sorting)

• 简单排序：冒泡排序、直接插入排序、简单选择排序（时间复杂度均为 $O(n^2)$）。
• 复杂排序：
  • 希尔排序：缩小增量排序。
  • 快速排序：基于分区交换，平均性能最好 $O(n\log_2n)$，但最坏为 $O(n^2)$。
  • 堆排序：建立大根堆/小根堆，通过“筛选”调整，时间复杂度 $O(n\log_2n)$。
  • 归并排序：分治法，稳定排序，$O(n\log_2n)$。
• 非比较排序：计数排序、基数排序。