导图社区 《数据结构》大纲
- 10
- 0
- 0
- 举报
《数据结构》大纲
这是一篇关于《数据结构》大纲的思维导图，主要内容包括：第一章 引言，第二章 表、栈和队列，第三章 树，第四章 哈希法，第五章 优先级队列，第六章 排序，第七章 不相交集合类，第八章 图。
编辑于2025-09-15 22:38:03- 书籍
- 数据结构
- 相似推荐
- 大纲
《数据结构》大纲
第一章 引言
1.1 数据结构基础
定义：无标准定义，通过抽象方法研究特定关系数据的存储与处理
研究内容：数据间逻辑关系及对应操作、逻辑关系的存储实现、存储模式下操作的运算实现
数据逻辑结构分类：
集合结构：元素间次序任意，仅“属于同一集合”联系
线性结构：数据元素有序序列，除首尾元素外，其余元素有唯一前趋和后继
树形结构：除根元素外，每个节点有且仅一个前趋，后继数目不限
图形结构：每个元素前趋和后继数目均不限
数据结构操作：创建、清除、插入、删除、搜索、更新、访问、遍历（含每种数据结构特定操作）
数据结构存储实现：
组成部分：数据元素存储、数据元素间关系存储
物理结构：存储结点（存数据元素）、逻辑结构机内表示（关系存储）、附加信息（如链表头结点）
基本存储方式：存储结点可用结构体/对象，采用泛型程序设计思想，重点讨论关系存储
关系存储方式：
顺序存储：用存储位置表关系，以数组实现
链接存储：用指针显式表关系，如单链表表线性关系
哈希存储：专用于集合结构，哈希函数关联数据元素与存储位置
索引存储：存储结点连续存放，设索引区域表结点关系
1.2 算法分析
核心关联：数据结构处理数据，存储方式下操作实现即算法，每种操作有多种实现
算法质量评价：正确性（实现预定功能）、易读性（便于调试修改）、健壮性（应对环境变化）、高效率（高时空性能），数据结构侧重时空性能
算法资源分析：
时间：程序运行时间，需避免过长耗时
空间：程序运行所需空间，需避免过大内存占用
关键概念：空间复杂度、时间复杂度、算法运算量计算、渐进表示法、时间复杂度计算、算法优化
空间复杂度：含固定空间需求（与问题规模无关）和可变空间需求（与数据量有关），按最坏情况处理，计算较简单
程序运行时间影响因素：问题规模与输入数据分布、编译器目标代码质量、计算机系统性能、算法优劣（关键因素）
有效算法重要性：差算法无实际意义，举例说明不同时间函数下计算机处理数据的效率差异，强调提高算法效率而非机器速度
时间复杂度：抽象度量运算量与问题规模关系，含最好、最坏、平均情况时间复杂度
算法运算量计算：选标准操作，确定给定输入下标准操作次数作为计算量
实例分析：以数组求最大值与d乘积为例，对比不同算法运算量
渐进表示法：
核心思想：不考虑具体运行时间函数，关注问题规模大时运行时间随规模变化规律，取运行时间函数数量级
定义：
大O：存在正常数c和N0，N≥N0时T(N)≤cF(N)，T(N)是O(F(N))
大Ω：存在正常数c和N0，N≥N0时T(N)≥cF(N)，T(N)是Ω(F(N))
大Ө：T(N)既是O(F(N))又是Ω(F(N))
小O：T(N)是O(F(N))但非Ө(F(N))
实例：T(n)=(n+1)²是O(n²)
F(N)选择：选简单函数形式，忽略低次项和系数
典型增长率：常量（c）、对数（logN）、对数平方（log₂N）、线性（N）、NlogN、平方（N²）、立方（N³）、指数（2ⁿ）
算法分类：
多项式时间算法：渐进时间复杂度有多项式时间限界
指数时间算法：渐进时间复杂度有指数时间限界
复杂度关系：O(1)＜O(logN)＜O(N)＜O(NlogN)＜O(N²)＜O(N³)；O(2ⁿ)＜O(N!)＜O(Nⁿ)
大O表示法计算：
步骤：定义标准操作，算标准操作次数得函数，取主项得大O表示
定理：
求和定理：T1(n)+T2(n)=O(MAX(f(n),g(n)))（T1(n)是O(f(n))，T2(n)是O(g(n))）
求积定理：T1(n)×T2(n)=O(f(n)×g(n))（T1(n)是O(f(n))，T2(n)是O(g(n))）
计算规则：
规则1：简单语句时间复杂度O(1)
规则2：条件语句时间复杂度O(1)+max(O(then子句),O(else子句))
规则3：循环语句时间复杂度为循环体运行时间×循环次数（含循环控制代价）
规则4：嵌套循环用求积定理，如双层循环时间复杂度O(n²)
连续语句：用求和定理，取复杂度高的作为整体复杂度
简化计算：找最复杂程序段算时间复杂度，即整个程序时间复杂度
1.3 典型实例 - 最大连续子序列问题
问题描述：给定整数序列（可负），找值最大的连续子序列，所有整数为负时和为0
实例：输入{-2,11,-4,13,-5,2}，答案20；输入{1,-3,4,-2,-1,6}，答案7
解法：
解法一（穷举法）：求所有可能子序列和，找最大值，时间复杂度O(n³)
解法二（O(n²)算法）：利用子序列和的递推关系，省略最内层循环
解法三（O(n)算法）：基于负子序列不构成最大连续子序列的特性，优化循环
1.4 面向对象的数据结构
过程化数据结构：分别介绍存储方式（记录）和操作实现（函数）
面向对象数据结构：
核心：封装数据结构的存储和处理过程成工具
优势：使用者仅需知逻辑特性，无需知存储和操作实现
学习要求：知存储和处理方法，懂封装以适配用户需求
课程采用面向对象方法
数据结构描述与实现：
逻辑特性：抽象类描述，指出提供的操作
实现：若干实现类，均从对应抽象类继承以保证逻辑特性
泛型程序设计：数据结构关注关系存储，数据元素可任意类型，类（含抽象类、非抽象类）均为模板
1.5 作业
第二章 7、8、27题
第二章 表、栈和队列
2.1 线性表
2.1.1 表的概念
定义：N个同特征结点A₀,A₁,…,Aₙ₋₁构成的集合，除A₀和Aₙ₋₁外，每个元素有唯一前趋（Aᵢ₋₁）和后继（Aᵢ₊₊₁），A₀无前趋，Aₙ₋₁无后继
术语：N为表大小，A₀为首结点，Aₙ₋₁为尾结点，空表（元素个数为0），位置（Aᵢ位置为i）
表的操作：创建（create()）、清除（clear()）、求长度（length()）、插入（insert(i,x)）、删除（remove(i)）、搜索（search(x)）、访问（visit(i)）、遍历（traverse()）
2.1.2 表的实现
线性表的顺序实现：
存储结构：结点存于连续存储空间，借助连续性按逻辑顺序存放，物理位置与逻辑位置一致
程序实现：用动态数组，需指针（指元素类型）、数组规模（容量）、元素个数（表长）三个变量
运算实现：
length()：返回length值
visit(i)：返回data[i]值
traverse()：输出data前length个元素
clear()：将length置0
create(maxSize)：申请maxSize大小动态数组
search(x)：遍历查找，返回位置或-1
insert(i,x)：表满时扩容（如扩大一倍），移动元素后插入，length加1
resize()：重新申请更大数组，拷贝原内容，释放原空间
remove(i)：移动元素覆盖被删元素，length减1
算法分析：
O(1)操作：length、visit、clear、create
O(n)操作：traverse、search、insert（最坏、平均）、remove（最坏、平均）
优缺点：定位访问性能好，插入删除需移动大量数据，适合静态、常定位访问的线性表
线性表的链接实现：
存储结构：每个结点存于独立存储单元，逻辑关系靠附加指针表示，物理位置可相邻或不相邻
分类：
单链表：每个结点含数据和next指针（指直接后继），尾结点next为空
双链表：每个结点含数据、prior（指直接前驱）和next（指直接后继）指针，头结点prior为空，尾结点next为空
循环链表：单循环链表（无头结点）、双循环链表（头结点prior指尾结点，尾结点next指头结点，无头尾结点）
单链表（带头结点）运算实现：
create()：申请头结点，头结点指针为空
clear()：释放所有结点空间，头结点指针置空
length()：遍历计数或用变量存长度
insert(i,x)：找到位置，插入新结点
remove(i)：找到位置，删除结点
search(x)：遍历查找，返回位置或-1
visit(i)：遍历找到位置，返回数据
traverse()：遍历输出数据
2.1.3 线性表类的实现
线性表抽象类：模板类，含clear()、length()、insert()、remove()、search()、visit()、traverse()纯虚函数及析构函数
顺序表类：
定义：继承list抽象类，含data（指针）、currentLength、maxSize成员，及doubleSpace()函数
构造函数：初始化数组，处理非法初始大小
析构函数：释放data数组
成员函数实现：clear()、length()、insert()、remove()、doubleSpace()等
双链表类：
定义：继承list抽象类，含内嵌node类（数据、prev、next指针），头指针、尾指针、currentLength，及move()函数
构造函数：创建头尾结点，初始化指针和currentLength
析构函数：clear()后释放头尾结点
成员函数实现：clear()、insert()、remove()、search()、visit()、traverse()、move()等
缺点：未利用双链表特点（如逆向查找）
2.1.4 STL中表的实现
STL简介：C++数据结构实现，称为集合或容器
线性表实现：
Vector：顺序实现，大小可增长
特性：维护原始数组、容量、大小，提供拷贝构造、赋值重载、修改容量、[]重载、迭代器等
定义：含theSize、theCapacity、objects成员，及构造、析构、resize()、reserve()、[]重载、push_back()、pop_back()、迭代器操作等函数
使用：示例代码展示初始化、push_back()、size()、capacity()、遍历（[]和迭代器）
List：双链表实现
特性：允许任意位置插入删除，支持双向迭代器
定义：含node结构体、theSize、head、tail、init()，及构造、析构、迭代器操作、size()、empty()、clear()、front()、back()、push_front()、push_back()、pop_front()、pop_back()等函数
使用：示例代码展示push_front()、push_back()、insert()、遍历
2.2 栈
2.2.1 栈的概念
定义：后进先出（LIFO）或先进后出（FILO）结构，最早（晚）到达结点最晚（先）删除，如乒乓球进盒出盒
相关概念：栈底（结构首部，结点最早到达）、栈顶（结构尾部，结点最晚到达）、进栈（Push，栈顶插入）、出栈（Pop，栈顶删除）、空栈（结点个数为0）
栈的ADT：模板类，含isEmpty()、push()、pop()、top()纯虚函数
2.2.2 栈的实现
栈的顺序实现：
用数组实现：
存储：用连续空间，栈顶在数组后端，需elem（指针）、top_p（栈顶下标）、maxSize（最大容量）成员
实现：seqStack类，含构造（初始化数组）、析构（释放数组）、isEmpty()、push()（满时扩容）、pop()、top()、doubleSpace()（扩容）函数
使用：示例代码展示push()、pop()、top()
用vector实现：
存储：vector存元素，数组头为栈底，数组尾为栈顶
操作：push用push_back()，pop用pop_back()，top用back()，isEmpty用empty()
实现：sqlStack类，继承stack类，含push()、pop()、top()、isEmpty()函数
使用：示例代码展示push()、pop()、top()
栈的链接实现：
用单链表直接实现：
存储：无头结点单链表，栈顶在表头，栈底在表尾
实现：linkStack类，含内嵌node类，elem（头指针）成员，及构造（elem置空）、析构（释放所有结点）、isEmpty()、push()（表头插入）、pop()（表头删除）、top()函数
使用：示例代码展示push()、pop()、top()
用list实现：
存储：list存元素，链表头为栈顶，链表尾为栈底
操作：push用push_front()，pop用pop_front()，top用front()，isEmpty用empty()
实现：linkStack类，继承stack类，含push()、pop()、top()、isEmpty()函数
2.2.3 栈的应用
递归函数的非递归实现：用栈模拟函数调用，函数调用时当前现场进栈，如快速排序非递归实现
符号平衡检查：
问题：检查括号（(、[、{）是否配对
算法：遇左括号进栈，遇右括号出栈比较，栈空或不匹配则出错
要求：设计checkBalance程序，支持输入文件名或命令行传参检查，输出错误及行号
实现：含Symbol结构体（存错误信息）、CommentType枚举（注释类型），及主函数、CheckBalance()、GetNextSymbol()、CheckMatch()、NextChar()、PutBackChar()、SkipComment()、SkipQuote()函数
表达式的计算：
中缀式与后缀式：前缀式（+ab）、中缀式（a+b）、后缀式（ab+），后缀式无需考虑运算符优先级
后缀式计算：初始化栈，读操作数进栈，读运算符则出栈两操作数运算后结果进栈，最后栈中剩余为结果
中缀式转后缀式：操作数立即输出，闭括号则出栈运算符至开括号（开括号出栈），开括号进栈，运算符按优先级处理（栈顶优先级高则出栈，直至低则进栈），结束后出栈剩余运算符
简单计算器实现：输入中缀表达式，计算正整数的加、减、乘、除、乘方，支持括号，用calc类（含表达式存储、BinaryOp()、operator=()、result()函数）
2.3 队列
2.3.1 队列的概念
定义：先进先出（FIFO）结构，早到达结点早离开，如银行排队、打印队列，可想象为管道，结点从队尾流入、队首流出
基本概念：出队（Dequeue，队首删除）、入队（Enqueue，队尾插入）、判队空（isEmpty）
队列的ADT：模板类，含isEmpty()、enQueue()、deQueue()纯虚函数
2.3.2 队列的实现
队列的顺序实现：
存储：用数组，元素下标0到MaxSize-1
组织方式：
队头在数组0位置：出队需移动大量数据，效率低
基本顺序实现：用front（队首指针，指下一个删除位置）和rear（队尾指针，指下一个插入位置），队空front=rear，队满rear=MaxSize
循环队列：逻辑上0是MaxSize，队满条件（rear+1）%MaxSize==front
问题解决：队满时创建更大数组，拷贝原内容，重置front和rear
作业要求：实现循环队列，自动扩容，从队列ADT继承
队列的链接实现：
存储：无头结点单链表，表头为队头，表尾为队尾，含front（头指针）和rear（尾指针）
操作实例：初始化（front=rear=NULL）、进队（表头/表中插入）、出队（表头删除）
链接队列设计：
数据成员：头尾指针（指结点，含数据和next指针）
成员函数：构造（front=rear=NULL）、析构（释放所有结点）、isEmpty()（front==NULL）、enQueue()（队尾插入）、deQueue()（队首删除）
实现：linkQueue类，继承queue类，含内嵌node类，front、rear成员，及构造、析构、isEmpty()、enQueue()、deQueue()函数
使用：示例代码展示enQueue()、deQueue()
顺序实现与链接实现比较：
时间：均常量时间完成基本操作，顺序队列因回绕处理较麻烦
空间：链接队列每个结点多指针字段，顺序队列有大量未用空间
2.3.3 队列的应用 - 排队系统的模拟
模拟简介：用计算机仿真现实系统操作，收集统计数据，如银行操作系统模拟
离散事件模拟：含客户到达、服务完毕客户离开两类事件，统计客户排队长度、等待时间等
基本方法：用概率函数产生客户到达时间和服务时间输入流，按到达时间排序，用“嘀嗒”（tick）作时间单位
时间驱动模拟：时钟从0开始，每步加1嘀嗒，检查事件，适合事件间隔小的情况，否则效率低
事件驱动模拟：
核心：每步跳到下一个事件发生时刻，处理事件并设当前时间
处理流程：
离开事件：收集统计信息，有等待客户则分配出纳员，计算离开时间并进事件集
到达事件：有空闲出纳员则分配并计算离开时间进事件集，否则进等待队列
优势：效率高，适合事件间隔大的情况
实现关键：
随机事件产生：用均匀分布（如客户到达间隔）、负指数分布（服务时间）、泊松分布（客户到达）
事件按时间排队：用优先级队列（按序插入）
随机事件产生：均匀分布用随机数产生器
优先级队列：在队列基础上按序插入，继承linkQueue类重写enQueue()
银行系统模拟实例：
假设：K个出纳员，客户到达间隔均匀分布，服务时间均匀分布
要求：计算客户平均等待时间
模拟过程：产生客户到达事件进事件队列，初始化等待队列、柜台状态、等待时间，处理事件（到达则分配柜台或进等待队列，离开则处理等待客户或柜台空闲），计算平均等待时间
工具准备：等待队列（普通队列）、事件队列（优先级队列）、随机事件产生函数
模拟器设计：
功能：获取模拟参数，计算平均等待时间
类定义：simulator类，含柜台数、客户到达参数、服务时间参数、模拟顾客数成员，及eventT结构体（事件时间、类型），构造函数（获取参数）、avgWaitTime()（计算平均等待时间）函数
main函数：创建simulator对象，输出平均等待时间
2.4 作业
P108 4、20、24、35题
第三章 树
3.1 树的基础
3.1.1 树的定义
定义：n（n≥1）个结点的有限集合T，有一个根结点，其余结点分m（m≥0）个互不相交集合（子树）
示例图：展示树的结构（A为根，子树含B、C、D等）
术语：结点、结点的度、叶子结点、内部结点、儿子结点、父亲结点、兄弟结点、祖先结点、子孙结点、结点层次、树的高度、有序树、无序树、森林
3.1.2 树的ADT
数据：同数据类型数据元素/结点的有限集合
关系：父子关系
操作：找根节点、找父结点、找第i个孩子、删除第i个孩子、建一棵树、树的遍历
3.1.3 树的存储结构
标准形式：每个结点含数据字段和K个指针字段（K为树的度）
广义标准形式：标准形式基础上加父亲结点指针场
示例：度数K=3的树广义标准存储（表格形式展示结点值、s1、s2、s3、p）
缺点：空指针字段多，浪费空间
3.1.4 树的链接存储结构
左儿子、右兄弟表示法：每个结点含数据、第一棵子树树根指针、兄弟结点指针，用二叉树表示树
示例图：展示树的左儿子右兄弟存储结构
3.1.5 树的遍历
前序遍历：访问根结点，前序遍历各子树
后序遍历：后序遍历各子树，访问根结点
示例：展示树的前序（A、B、L、E、C、F、D、G、I、H）和后序（L、E、B、F、C、I、G、H、D、A）遍历结果
3.1.6 树的应用 - 目录结构遍历
应用场景：操作系统目录结构（如Unix、Windows/DOS），列出目录及子目录文件名，深度d文件名缩进d个制表符
实现：前序遍历，listAll()函数（打印名称，若为目录则遍历子目录）
示例：展示目录结构及遍历输出
3.2 二叉树
3.2.1 二叉树的概念
定义：结点的有限集合，空或由根及两棵互不相交左、右子树构成，左、右子树也是二叉树，严格区分左右子树
基本形态：空二叉树、根和空左右子树、根和左右子树、根和左子树、根和右子树
结点总数为3的二叉树不同形状：展示所有可能形状
常用操作：创建空树、找根节点、找父结点、找左孩子、找右孩子、建二叉树（给左右孩子和根）、删除左孩子、删除右孩子、遍历
3.2.2 二叉树的性质
性质1：非空二叉树第i层最多2ⁱ⁻¹个结点（i≥1），示例及证明（归纳法）
性质2：高度为k的二叉树最多2ᵏ⁻¹个结点，证明（求和2⁰到2ᵏ⁻¹）
性质3：非空二叉树，叶子结点数n₀=度数为2的结点数n₂+1，证明（结点总数、树枝总数关系推导）
3.2.3 满二叉树和完全二叉树
满二叉树：高度为k且有2ᵏ⁻¹个结点的二叉树，任意层结点数达最大值，示例图
完全二叉树：满二叉树最底层自右至左去若干结点，特点（叶结点在最低两层，任一结点右子树高k则左子树高k或k+1），示例图（完全与非完全对比）
完全二叉树高度特性（性质4）：n个结点完全二叉树高度k=⌊log₂n⌋+1，证明（范围推导）
完全二叉树编号特性：n个结点完全二叉树按层序编号（根1），对编号i结点（1≤i≤n）：
i=1为根，i>1则父结点编号⌊i/2⌋
2i>n则无左儿子，否则左儿子编号2i
2i+1>n则无右儿子，否则右儿子编号2i+1
示例图：展示完全二叉树编号及对应关系
3.2.4 二叉树的遍历
前序遍历：空则空，否则访问根，前序遍历左子树，前序遍历右子树
中序遍历：空则空，否则中序遍历左子树，访问根，中序遍历右子树
后序遍历：空则空，否则后序遍历左子树，后序遍历右子树
示例：展示树的前序（A、L、B、E、C、D、W、X）、中序（B、L、E、A、C、W、X、D）、后序（B、E、L、X、W、D、C、A）遍历结果
前序+中序唯一确定二叉树：示例（前序A、B、D、E、F、C，中序D、B、E、F、A、C），逐步构建二叉树
3.2.5 二叉树的存储
顺序存储：
完全二叉树：按编号存储，省略左右孩子字段，示例图（编号与数组对应）
普通二叉树：修补成完全二叉树再存储，示例图（普通树与修补后数组）
右单支树实例：展示右单支树的顺序存储（大量空值）
链接存储：
标准形式（二叉链表）：结点含data、left、right指针，示例图
广义标准形式（三叉链表）：结点含data、left、right、parent指针，示例图
示例：展示二叉树的标准和广义标准链接存储
3.2.6 二叉树类的实现
结点类Node设计：内嵌于树类，含data、left、right指针，构造、析构函数
二叉树类BinaryTree设计：
存储：指向根结点的指针
操作：判空、清空、遍历、求高、求规模、创建、归并
成员函数实现（递归）：
求规模：左子树规模+右子树规模+1
求高度：1+max(左子树高度,右子树高度)
三种遍历：递归实现
树的删除：递归删除左右子树，再删根
递归函数设计：公有函数（无参）调用私有递归函数（带参）
类定义：template <class Type> class BinaryTree，含Node结构体，root成员，及构造、析构、getRoot()、getLeft()、getRight()、makeTree()、delLeft()、delRight()、delTree()、isEmpty()、size()、height()、printPreOrder()、printPostOrder()、printInOrder()、createTree()函数，私有成员函数（height()、delTree()、size()、printPreOrder()、printPostOrder()、printInOrder()）
创建树（createTree()）：
过程：输入根结点，用队列存新结点，依次出队输入儿子（特定值表空）
示例：展示队列变化及树的构建
代码实现：用linkQueue，输入结点值，处理儿子结点
二叉树类应用：示例代码（创建树、求高、求规模、遍历、归并），执行实例（输入及输出结果）
3.2.7 二叉树遍历的迭代器类
迭代器需求：提供按某种次序访问树元素的工具（如++访问下一元素），对应三种遍历
迭代器类行为规范：TreeIterator类，含构造、析构、First()（首结点）、operator++()（下一结点）、operator+()（判空）、operator()()（返回当前数据）函数，保护成员T（二叉树）、current（当前结点指针）
前序遍历迭代器（Preorder类）：
继承TreeIterator，含栈（存结点指针）成员
非递归算法：根进栈，出栈访问，右、左儿子（非空）进栈，重复至栈空
构造函数：初始化栈，根进栈
operator++()：栈空则current置空，否则出栈current，右、左儿子进栈
First()：栈清空，根进栈，调用operator++()
后序遍历迭代器（Postorder类）：
继承TreeIterator，含栈（存StNode，含结点指针和TimesPop）成员
算法：结点进栈（标志0），出栈处理左子树（标志1），再出栈处理右子树（标志2），标志2则访问
StNode结构体：含node（结点指针）、TimesPop（弹出次数）
构造函数：栈push根结点（StNode）
operator++()：栈空则current置空，否则循环出栈，TimesPop加1，标志3则current=node，否则push回栈，处理左/右子树
First()：栈清空，根进栈，调用operator++()
中序遍历迭代器（Inorder类）：
继承Postorder，仅重写operator++()
算法：类似后序，标志2则访问，处理右子树
operator++()：栈空则current置空，否则循环出栈，TimesPop加1，标志2则current=node，push右儿子（非空），否则push回栈，处理左子树
迭代器应用：示例代码（创建树，用前序、中序、后序迭代器遍历）
3.2.8 二叉树的应用 - 表达式树
表达式树：算术表达式表示为二叉树，后序遍历得结果，示例图（(4-2)*(10+(4+6)/2)+2）
设计目标：用表达式树计算表达式
构建过程：递归构建，括号内子表达式为子树，处理运算数、运算符（按优先级）
类设计：calc类，含node结构体（type、data、lchild、rchild），root成员，及create()、postOrder()、getToken()、result()函数，公有构造（从表达式构建）、result()（计算结果）函数
getToken()：从表达式取语法单位（DATA、ADD、SUB、MULTI、DIV、OPAREN、CPAREN、EOL），处理空格、数字、运算符、括号
create()：递归构建表达式树，处理运算数、括号、运算符（按优先级）
postOrder()：后序遍历输出（验证表达式树）
result()：递归计算，后序遍历，运算数返回data，运算符计算左右子树结果
应用：示例代码（创建calc对象，计算表达式结果）
问题：未考虑表达式不正确情况
3.3 哈夫曼树与哈夫曼编码
3.3.1 哈夫曼树的用途
数据压缩：可变长编码，常用字符短编码，示例（字符频率a(10)、e(15)等，定长需174bit，哈夫曼编码需146bit）
哈夫曼编码：频率大字符靠近树根，路径（左0右1）为编码，示例图
3.3.2 哈夫曼算法
步骤：
给定n个权值集合F={T₁,T₂,…,Tₙ}
初始A=F
循环n-1次：选权值最小两结点作内部结点bᵢ的左右儿子，bᵢ权值为两儿子和，A中删两结点加bᵢ
最终A中剩余结点为根
示例：a(10)、e(15)等字符构建哈夫曼树，示例图
哈夫曼编码生成：从叶子往根，左0右1，示例（a的编码001）
3.3.3 哈夫曼树的存储
特点：编码元素为叶结点，其他为度2结点，大小2n-1（n为编码元素数）
存储：大小2n数组，0不用，根存1，叶结点存n+1到2n，每个元素存数据、权值、父、左右孩子位置
示例：表格展示哈夫曼树存储（值、权、父、左、右）
生成过程：逐步展示数组元素变化
3.3.4 哈夫曼树类
结点定义：Node结构体（data、weight、parent、left、right）
返回编码存储结构：hfCode结构体（data、code）
哈夫曼树类定义：hfTree类，含elem（Node数组）、length成员，及构造函数（建哈夫曼树）、getCode()（获取编码）、析构函数
构造函数：初始化叶结点，循环构建内部结点（选最小两权值结点）
getCode()：从叶结点往根，记录路径（左0右1），生成编码
使用：示例代码（生成字符集a(10)等的哈夫曼编码，输出结果）
3.4 二叉排序树
3.4.1 二叉排序树的定义
定义：空或满足：任意结点p，左子树（非空）所有结点关键字< p关键字，右子树（非空）所有结点关键字> p关键字，左右子树也是二叉排序树
示例图：展示二叉排序树（含字符、数值）
3.4.2 二叉排序树的操作
查找：根等于则成功，小于查左子树，大于查右子树，示例（查找122、110等）
查找递归描述：空返回false，根等于返回true，小于查左，大于查右
插入：空则新结点为根，非空则查找父结点，按大小插为叶子，示例（序列122、99等构建树）
插入递归实现：空则插根，小于插左，大于插右
删除：
删除叶结点：直接删，改父指针为空
删除有一个儿子的结点：儿子取代被删结点位置
删除有两个儿子的结点：选左子树最大或右子树最小结点为替身，复制数据，删替身
示例图：展示三种删除情况
删除递归实现：空返回，小于删左，大于删右，等于则（两儿子则右子树最小替代并删最小，否则儿子取代）
3.4.3 二叉排序树类的设计
类定义：BinarySearchTree类，含BinaryNode结构体（element、left、right），root成员，及构造、析构、findMin()、findMax()、contains()、isEmpty()、makeEmpty()、insert()、remove()、operator=()、printInOrder()函数，私有成员函数（insert()、remove()、findMin()、findMax()、contains()、makeEmpty()、clone()、printInOrder()）
设计特点：内嵌BinaryNode类，root为数据成员，公有函数调用私有递归函数
成员函数实现：
contains()：递归查找
insert()：递归插入
findMin()：递归找最左结点
findMax()：非递归找最右结点
remove()：递归删除
printInOrder()：递归中序遍历
析构函数：调用makeEmpty()
makeEmpty()：递归删除所有结点
3.5 AVL树（平衡二叉树）
3.5.1 平衡二叉树的定义
背景：树退化为链表时性能差，需平衡树
平衡因子：结点左子树高-右子树高，空树高-1
平衡二叉树：每个结点平衡因子为+1、-1、0，或左右子树高最多差1
高度特性：高度至多约1.44log(N+2)-1.328
示例图：展示平衡树与非平衡树（平衡因子）
3.5.2 平衡树的操作 - 插入
插入过程：同二叉排序树，插入后可能：
不破坏平衡：自底向上修改平衡度，某节点平衡度不变则停止
破坏平衡：需调整
示例：插入29（不破坏）、插入2（破坏）
插入引起不平衡的情况：
LL：左孩子左子树插入
LR：左孩子右子树插入
RL：右孩子左子树插入
RR：右孩子右子树插入
调整方法：
LL/RR（单旋转）：LL则左儿子为根，原根为右子树，原右儿子为原根左子树；RR则相反，示例图
LR/RL（双旋转）：LR则先旋转儿子和孙子，再旋转根和新儿子；RL则相反，示例图
3.5.3 AVL树类的实现
节点定义：AvlNode结构体（element、left、right、height）
求节点高度：height(t)，空返回-1
插入：insert(x, t)，递归插入，判断平衡因子，执行对应旋转（LL、LR、RR、RL），更新高度
旋转函数：
rotateWithLeftChild()（LL旋转）
rotateWithRightChild()（RR旋转）
doubleWithLeftChild()（LR旋转，先RR再LL）
doubleWithRightChild()（RL旋转，先LL再RR）
类定义：AvlTree类，含AvlNode结构体，root成员，及构造、析构、isEmpty()、findMin()、findMax()、contains()、insert()、remove()、makeEmpty()、printTree()函数，私有成员函数（insert()、remove()、findMin()、findMax()、contains()、makeEmpty()、clone()、rotateWithLeftChild()、rotateWithRightChild()、doubleWithLeftChild()、doubleWithRightChild()、height()）
3.5.4 平衡树的其他操作与性能
删除：迟删除（标记）
查找性能：与树高成正比，O(logN)
定理：N个结点平衡树高h满足log₂(N+1)≤h≤1.44log₂(N+1)-0.328，证明（满二叉树、最少结点树推导）
3.6 伸展树
3.6.1 平衡树的缺陷
需额外平衡信息
实现复杂，插入删除代价大
未利用90-10规则（90%访问针对10%数据）
3.6.2 均摊分析法
定义：限定M个连续操作代价，均匀分布到每个操作
示例：数组加倍，M个操作总代价O(M)
3.6.3 伸展树的概念
核心：访问节点后通过旋转向根移动，常访问节点近根，有平衡副作用
基本想法：连续与父节点旋转至根，示例（访问3后的旋转）
基本方法缺陷：可能出现长糟糕访问序列，示例（插入1-N再访问1-N）
3.6.4 伸展策略
目标：自底向上伸展使树平衡，得对数均摊上界
策略：通过自底向根旋转，分三种情况（zig、zig-zig、zig-zag）
旋转类型：
zig：x父为根，单旋转，示例图
zig-zag：x是右孩子，父是左孩子（或反之），双旋转，示例图
zig-zig：x和父同为左/右孩子，先旋转父和祖父，再旋转x和父，示例图
实例：插入1-N后访问1，树高度降低，示例图
优势：常访问节点近根，均摊时间O(logN)
3.7 B树
3.7.1 B树的背景
场景：数据量大，内存放不下，需外存数据结构，减少磁盘访问次数
示例：10⁷条记录，非平衡树最坏10⁷次磁盘访问（463小时），平均32次（5秒），典型100次（16秒）
解决方法：M叉查找树，降低树高，log_M N
3.7.2 B树的定义
M阶B树：
数据存叶子
非叶子结点至多M-1个键（引导查找）
根或为叶子，或有2-M个儿子
非根非叶结点儿子数⌈M/2⌉-M
所有叶子同层，有⌈L/2⌉-L个数据项
示例图：5阶B树，展示节点（磁盘块）、键、儿子
3.7.3 L和M的选择
示例：块容量8192字节，键32字节，分支4字节，M=228（非叶结点），L=32（叶子，每条记录256字节）
规模：10⁷条记录，至多625000个叶子，3-4层索引
3.7.4 B树的插入
过程：
找插入叶结点
叶不满：插入并调整顺序
叶满：分裂为两个半满叶子，更新父节点
父满则继续分裂，最坏分裂根（根允许2孩子）
示例：插入57、55、40，展示树的变化
3.7.5 B树的删除
过程：
找删除项并删除
叶子元素数低于最小：
邻居非最小则借
邻居最小则合并，父失去儿子，若父低于最小则继续
根只剩一个儿子则根删除，儿子为新根
示例：删除99，展示树的变化
3.7.6 B树的时间效益
高度：log_{⌈M/2⌉} (2N/L)，3-4层
操作：查找至多5次读磁盘，插入删除多1次写，分裂/归并额外4次写（均摊可忽略）
3.8 STL中的集合与映射
3.8.1 集合（set）
特性：不允许重复元素的有序容器
遍历：iterator和const_iterator
操作：与vector、list基本类似
示例代码：展示insert()、size()、遍历（iterator），输出结果
3.8.2 映射（map）
特性：存储关键字（唯一）-值序偶，不同关键字可对应相同值
操作：与set类似
应用：找改一个字母变另一个字的单词（如wine→fine等），示例（词典存vector，结果存map<字符串, vector<字符串>>）
实现：computeAdjacentWords()（构建map）、printHighChangeables()（输出结果），算法优化（按长度分组）
3.9 作业
P175 4.9、4.10、4.19题
家谱管理系统：设置家谱、添加子孙、修改子孙状态、查询
第四章 哈希法
4.1 基本概念
背景：小非负整数可直接用数组（初始化、insert、find、remove均O(1)），但大整数、字符串不适用
解决方案：
哈希函数：将大数字映射为小下标
字符串处理：解释为整数
定义：哈希法（散列法），直接按关键字找结点，时间O(1)，不支持有序操作
4.2 哈希函数
定义：H(key)，值域0-m-1，冲突少
常用哈希函数：
直接地址法：H(key)=key或a×key+b，示例（关键字{100,400等}，H(x)=x或x/100）
除留余数法：H(key)=key MOD p或+ c（p≤m素数），示例（m=1024，p=1019），选p为质数理由（避免空间浪费）
数字分析法：选数字分布均匀的位作地址
哈希函数选择：计算时间、关键字长度、散列表长度、关键字分布、查找频率
4.3 冲突解决
冲突：多个关键字映射到同一存储单元
解决方法：
闭散列表（利用本散列表空余单元）：
线性探测法：H(key)=key MOD 11，冲突则探测下一个空单元，示例（关键字17、60、29、38）
删除和查找：查找（遍历至空或找到），删除（迟删除，避免查找问题）
问题：初级聚集（同哈希地址）、二次聚集（不同哈希地址争单元），最坏O(n)
哈希表定义：HashTable类，含HashEntry结构体（element、info（ACTIVE/EMPTY/DELETED）），array（vector）、currentSize成员，及构造、contains()、makeEmpty()、insert()、remove()函数，私有成员函数（isActive()、findPos()、rehash()、myhash()）
二次探测法：地址序列i+1²,i+2²,...，定理（表大小素数，表至少半满则可插入，无重复探测），证明（反证法）
再次散列法：用第二个哈希函数，第i次冲突地址f(i)=i×hash2(x)，hash2(x)=R-(x MOD R)（R<表长素数）
开散列表（链接法）：碰撞结点存散列表外线性表，示例图（同义链）
基于链地址法的哈希表：HashTable类，含theLists（vector<list<HashedObj>>）、currentSize成员，及构造、contains()、makeEmpty()、insert()、remove()函数，私有成员函数（rehash()、myhash()）
重新散列：负载因子>0.5则扩容一倍，重新计算哈希值插入
4.4 作业
P208 1题
第五章 优先级队列
5.1 优先级队列模型
定义：至少支持insert（enQueue）、deleteMin（deQueue）操作的数据结构
5.2 优先级队列的简单实现
单链表：
插入在头，删除遍历（O(n)）；有序单链表插入找位置（O(n)），删除在头（O(1)）
二叉查找树：插入、删除O(logn)，但无需所有元素有序
5.3 二叉堆
5.3.1 二叉堆的定义
定义：完全二叉树，满足：
最小化堆：kᵢ≤k₂ᵢ且kᵢ≤k₂ᵢ₊₁（i=1..⌊n/2⌋）
最大化堆：kᵢ≥k₂ᵢ且kᵢ≥k₂ᵢ₊₁（i=1..⌊n/2⌋）
示例：最小化堆{2,3,4,5,7,10,23,29,60}，最大化堆{12,7,8,4,6,5,3,1}，示例图
5.3.2 二叉堆的特性
结构性：完全二叉树
有序性：最小化/最大化堆特性
讨论基础：最小化堆
5.3.3 堆的应用
优先级队列：最大/最小元素为根
堆排序：建堆，取根，调整堆，重复至堆空
5.3.4 堆的主要操作
建堆：
方法：N次插入（O(NlogN)），或逆向层次调用percolateDown（O(N)）
示例图：展示建堆过程
插入：
过程：队尾插入，向上过滤（percolate up）至满足有序性
示例图：展示插入过程
代码：insert(x)，扩容，hole=currentSize++，向上比较交换
时间：最坏O(logN)，平均2.6次比较，上移1.6层
删除：
过程：根删除，最后元素放根，向下过滤（percolate down）至满足有序性
示例图：展示删除过程
代码：deleteMin()，deleteMin(minItem)，percolateDown(hole)
时间：最坏、平均O(logN)
5.3.5 二叉堆类的实现
类定义：BinaryHeap类，含currentSize、array（vector）成员，及构造、isEmpty()、findMin()、insert()、deleteMin()、deleteMin(minItem)、makeEmpty()函数，私有成员函数（buildHeap()、percolateDown()）
构造函数：默认构造，从vector构造（buildHeap()）
buildHeap()：从currentSize/2逆向调用percolateDown()
percolateDown()：向下过滤，找较小儿子交换，直至满足有序性
5.4 优先级队列的应用
5.4.1 选择问题
问题：N个元素表找第k个大元素
解法：
解法一：排序取第k个，O(N²)
解法二：建堆，k次deleteMin，O(N+klogN)=O(NlogN)
解法三：找第k个大，读k个元素建堆，剩余元素比根大则插入删根，O(Nlogk)
5.4.2 事件驱动的模拟
场景：银行排队系统，生成到达事件，处理最早事件（生成服务时间回事件队列）
实现：事件队列设为优先级队列（时间为优先级）
5.5 D-堆
定义：每个节点k个儿子，树较矮
操作：
插入：O(log_d N)
删除：O(dlog_d N)（d个元素找最小）
优缺点：插入快，运行时间长（无移位优化）
用途：插入比删除多的队列，大队列存外存
5.6 左堆
5.6.1 左堆的定义
空路径长度（npl）：x到不满两孩子节点的最短路径，叶子npl=0，空npl=-1
左堆：每个节点左孩子npl≥右孩子npl，左倾斜，示例图（左堆与非左堆）
5.6.2 左堆的主要操作 - 归并
递归方法：
根大的堆与根小的堆右子树归并
归并后若违反左堆定义则交换左右子树
终止：某堆空则返回另一堆
示例图：展示归并过程（H1、H2归并）
5.6.3 左堆类的实现
类定义：LeftistHeap类，含LeftistNode结构体（element、left、right、npl），root成员，及构造、析构、isEmpty()、findMin()、insert()、deleteMin()、deleteMin(minItem)、makeEmpty()、merge()、operator=()函数，私有成员函数（merge()、merge1()、swapChildren()、reclaimMemory()、clone()）
公有merge()：合并两棵左堆，rhs置空
私有merge()：根小的与根大的右子树归并，调用merge1()
merge1()：递归归并右子树，交换左右子树（若需），更新npl
5.7 斜堆
定义：满足堆有序性，不满足结构性，无需npl，右路径任意长
时间：最坏O(N)，M个操作均摊O(MlogN)，每个操作均摊O(logN)
归并：类似左堆，归并后无条件交换左右子树（除右路径最大节点）
示例图：展示归并过程
优点：无需npl，实现简单
5.8 贝努里队列
5.8.1 贝努里树与队列定义
贝努里树：B₀单节点，Bₖ由两棵Bₖ₋₁组成，满足堆有序性，示例图（B₀、B₁、B₂、B₃）
贝努里树特性：Bₖ有2ᵏ个节点，第d层节点数为贝努里系数
贝努里队列：贝努里树集合，每个高度至多一棵，对应元素个数二进制表示，示例图（6、7个元素队列）
5.8.2 贝努里队列的操作
归并：
低到高归并同高度树，三棵则留一棵归并另两棵
同高度树归并：根小的为根，根大的为子树
时间：O(logN)
示例：归并H1、H2，展示过程
插入：
单节点树与原队列归并，O(logN)（最坏），平均O(1)（进位终止）
删除：
找最小根树T，删T，T删根，归并T与原队列
示例：删除最小元素，展示过程
5.8.3 贝努里队列的存储
树：孩子兄弟链
森林：指向树根的指针线性表
示例图：展示队列存储结构
5.8.4 贝努里队列类的实现
类定义：BinomialQueue类，含BinomialNode结构体（element、leftChild、nextSibling），currentSize、theTrees（vector<BinomialNode*>）成员，及构造、析构、isEmpty()、findMin()、insert()、deleteMin()、deleteMin(minItem)、makeEmpty()、merge()、operator=()函数，私有成员函数（findMinIndex()、capacity()、combineTrees()、makeEmpty()、clone()）
5.9 STL中的优先级队列
头文件：queue
类模版：priority_queue
实现：二叉堆
主要成员：push()、top()、pop()、empty()、clear()
5.10 作业
P251 2、3、19、32、34题
第六章 排序
6.1 引言
假设：元素存数组，N为元素个数，元素支持<、>操作，基于比较的排序算法
6.2 插入排序
6.2.1 简单插入排序
原理：每步将待排序对象按关键字插入前面已排序序列
过程：1≤j<n，将a[j]与a[0..j-1]从右到左比较，插入合适位置
示例图：展示排序过程
算法：insertionSort(vector<Comparable> &a)，双层循环，tmp暂存a[p]，移动后插入
时间复杂度：O(N²)（逆序最坏），O(N)（已排序最好），适合元素少、近排序的情况
6.2.2 折半插入排序、希尔排序
折半插入排序：找插入位置用折半查找，减少比较次数，仍需移动元素，O(N²)
希尔排序：见6.4节
6.3 简单排序的下界
逆序：i<j但Aᵢ>Aⱼ的有序偶，示例（{8,5,9,2,6,3}有10个逆序）
定理：N个不同元素数组平均逆序数N(N-1)/4，证明（数组与逆数组逆序总数）
定理：通过交换相邻元素排序的算法平均需Ω(N²)时间，证明（交换消除一个逆序）
6.4 希尔排序
思想：改进插入排序，先比较远元素，再近元素，逐步逼近基本插入排序
算法思想：
取gap<n，分gap个子序列（距离gap），各子序列简单插入排序
缩小gap，重复，直至gap=1
示例图：展示排序过程
性质：hk-有序数组经hk-1-排序后仍hk-有序
希尔增量：gap从N/2平分至1
算法：shellsort(vector<Comparable> &a)，双层循环，gap递减，内层插入排序
时间复杂度：希尔增量最坏O(N²)，平均O(N³/²)，依赖增量序列
6.5 堆排序
原理：
buildHeap建堆（O(N)）
N次deleteMin取元素，结果排序（O(NlogN)）
空间问题：
问题：需两倍空间（堆+结果）
解决：deleteMin后堆缩小，最后位置存删除元素，用最大堆生递增排序
示例图：展示排序过程（59,36等排序）
算法：heapsort(vector<Comparable> &a)，buildHeap，交换根与最后元素，percolateDown，重复
6.6 归并排序
6.6.1 归并排序原理
思想：合并两个已排序有序表，分治法
合并实例：展示两个有序数组合并过程
归并排序法：
N=1则已排序
否则递归归并排序前、后一半，合并两有序数组
示例图：展示归并排序过程
6.6.2 归并排序的实现
包裹函数：mergeSort(vector<Comparable> &a)，创建tmpArray，调用带参mergeSort
带参mergeSort：mergeSort(a, tmpArray, left, right)，递归排序左右，合并
merge函数：merge(a, tmpArray, leftPos, rightPos, rightEnd)，合并两有序子数组，拷贝回原数组
时间复杂度：O(NlogN)，需额外空间
6.7 快速排序
6.7.1 快速排序原理
步骤：
S空或1则返回
选pivot（中心点）
分S-{v}为L（≤v）、R（≥v）
返回Quicksort(L)+v+Quicksort(R)
关键：选择中心点、划分
6.7.2 选择中心点
错误方式：选第一个元素，已排序/逆序时划分差，O(N²)
安全选择：随机选，耗时
三个元素中值划分：选首、中、尾中值，示例（8,1,4等选6），避免已排序情况差划分
6.7.3 划分方法
过程：
pivot放最后，i左到右，j右到左，i停大元素，j停小元素，未交叉则交换，否则pivot与i交换
示例：展示划分过程（8,1,4等）
6.7.4 小规模数组优化
小规模（≤10）用插入排序，递归终止，提升效率
6.7.5 快速排序程序
包裹函数：quicksort(vector<Comparable> &a)，调用带参quicksort
median3函数：选三个元素中值，放right-1
带参quicksort：quicksort(a, left, right)，小规模用插入排序，否则选pivot，划分，递归排序左右
时间复杂度：
最坏：O(N²)（pivot最小/最大）
最好：O(NlogN)（均匀划分）
平均：O(NlogN)
6.7.6 快速排序在选择问题中的应用
Quickselect(S,k)：
S1则返回唯一元素
选pivot，划分L、R
k≤|L|则递归Quickselect(L,k)，k=|L|+1则返回pivot，否则递归Quickselect(R,k-|L|-1)
时间：最坏O(N²)，平均O(N)
6.8 间接排序
背景：大对象频繁交换耗时
解决方案：用指针数组指向对象，交换指针，排序后按指针重排对象
6.9 排序的通用下界
结论：基于比较的排序算法至少需O(NlogN)时间
证明：
输入为1..N的排列，共N!种
比较次数决定排列，每次比较减半可能排列，需log(N!)次比较
log(N!)≈NlogN-1.44N，故至少O(NlogN)
6.10 口袋排序法
场景：输入值1-M的正整数
原理：设size=M的count数组，读入Ai则count[Ai]++，扫描count输出
时间复杂度：O(M+N)
6.11 外排序
6.11.1 外排序模型
设备依赖性：考虑磁带，需2-3个磁带机
6.11.2 简单算法（两路归并）
假设：4磁带A1,A2,B1,B2，内存存M个记录
过程：
读M个记录排序，轮流写B1,B2（run），回绕
归并B1,B2的run，轮流写A1,A2，回绕
重复，直至一个run（长度N）
示例图：展示初始、归并后磁带配置
时间：log(N/M)次归并，加初始run构造
6.11.3 多路归并
原理：K路归并减少归并次数，用优先级队列找K个元素最小
示例：6磁带3路归并，展示过程
时间：log_K (N/M)次归并
6.11.4 多阶段归并
原理：K+1磁带实现K路归并，非均匀分布run
示例：3磁带34个run，分布21、13，展示归并过程
初始run分布：斐波纳契数，不足则填虚拟run
6.11.5 置换选择
原理：生成更长run，读M元素建堆，deleteMin输出，读下元素比输出大则插入，否则存空余位置，堆空则新run（用空余元素）
示例：81,94等生成run，展示过程
6.12 作业
P306 3、12、16、20、30、38、52题
第七章 不相交集合类
7.1 等价关系
关系：集合S上，aRb真/假
等价关系：自反性（aRa）、对称性（aRb↔bRa）、传递性（aRb∧bRc→aRc）
7.2 动态等价问题
背景：等价关系隐式，需高效处理find（找等价类）、union（合并等价类）
等价类：S中子集，含所有相关元素，形成分割
操作：find、union，不相交集（并查集）
7.3 基本的数据结构
表示：森林（树），根为等价类名，数组存父节点（s[i]=-1为根）
操作：
union：归并两棵树（根为子树），O(1)
find：找根，O(N)（最坏）
示例图：展示union过程（union(4,5)、union(6,7)、union(4,6)）
7.4 智能并算法
背景：基本算法find线性，M操作O(MN)
智能并：
按规模归并：小树为大树子树，根存负规模
示例图：展示普通并与按规模并的区别
定理：按规模归并，节点深度≤logN
按高度归并：浅树为深树子树，根存高度
按规模并类的实现：
类定义：DisjointSet类，含set（数组）、size成员，及构造、find()、Union()函数
成员函数：构造（初始化set为-1）、find()（找根）、Union()（按规模归并）
使用：示例代码（find、Union操作，输出结果）
7.5 路径压缩
背景：并/查算法M操作O(MlogN)，可改进
路径压缩：find时将路径上节点父节点改为根，示例图
兼容性：与按规模归并兼容，与按高度归并不完全兼容（用秩）
性能：M操作均摊O(Mα(N))（α(N)反阿克曼函数，≤5）
7.6 应用 - 迷宫问题
场景：M×N矩形单元迷宫，入口左上，出口右下，生成迷宫（拆墙至连通）
算法：
初始：全墙，单元不连通
随机选墙，分隔单元不连通则拆墙，归并等价类
重复至全连通
实现：
连通为等价关系，单元编号，邻接单元判等价类，拆墙归并
示例图：展示初始、拆墙过程
7.7 作业
P335 1、4题
第八章 图
8.1 图的定义
8.1.1 图的基本定义
定义：G=(V,E)，V顶点集合，E边（弧）集合
分类：
有向图：边有方向，<A,B>≠<B,A>，示例图
无向图：边无方向，(A,B)，示例图
加权图：边有权值，<Vi,Vj,W>/(Vi,Vj,W)，示例图
8.1.2 图的术语
邻接：有向图Vi邻接到Vj，无向图Vi与Vj邻接
度：无向图邻接边数；有向图入度（入边数）、出度（出边数）
子图：G'=(V',E')，V'⊆V，E'⊆E，示例图
无向图连通性：
路径：顶点序列
回路/环：首尾相同路径
简单回路/环：除首尾无重复顶点
连通：两点有路径
连通图：任意两点连通
连通分量：极大连通子图，示例图
有向图连通性：
强连通图：任意两点连通
强连通分量：极大强连通子图
弱连通图：视为无向图连通，示例图
完全图：无向完全图（n(n-1)/2边），有向完全图（n(n-1)边），示例图
有向无环图（DAG）：无环的