跳到正文

CSCI2100

数据结构

链表、栈与队列、动态数组、哈希、优先队列、二叉搜索树、平衡搜索树与多路搜索树、Trie、不相交集合、排序、图算法及算法分析。

19 章 · 30 节EN · 繁 · 简
我的课程笔记

你的进度

0/ 30 节已标记完成

下一节: 不相交集合:划分、森林与并查集

完成记录保存在此浏览器中。

这门课在网上

CSCI2100 笔记里的内容

定理卡
69
定义
41
反例
39
概念视角
20
思想史
0
证明透视
35

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 30 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

在网上定理卡 69 · 定义 41 · 反例 39 · 概念视角 20 · 证明透视 35

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 30 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

第 1 章 · 1 节

不相交集合

划分与并查集

定理 3 · 定义 1反例 2视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 1.1

    不相交集合:划分、森林与并查集

    用父指针森林表示逐步合并的群组,证明连接根与路径压缩的正确性,并分析按大小合并。

第 2 章 · 3 节

线性数据结构

队列不变量、摊还分析及链表环检测。

定理 7 · 定义 3反例 4视角 2证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 2.1

    用两个栈建立先进先出队列

    证明队列不变量,并计算偶尔昂贵的转移成本。

  2. 2.2

    不使用访问集合检测链表中的环

    追踪 Floyd 的指针,证明相遇原因,并定位及安全移除环。

  3. 2.3

    双栈队列:不变量与摊还成本

    追踪队首观察、转移循环与摊还成本。

第 3 章 · 2 节

优先队列

堆不变量、插入及移除最小值。

定理 6 · 定义 2反例 2视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 3.1

    二叉最小堆与优先队列

    证明二叉最小堆不变量,分析插入及移除最小值。

  2. 3.2

    自底向上建立最小堆

    证明下滤的正确性及原地建立堆的线性时间界。

第 4 章 · 2 节

搜索树的顺序统计量

维护子树大小并按排名选取键。

定理 2 · 定义 2反例 2视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 4.1

    在搜索树中按排名选取

    证明排名选取,并在插入、删除及旋转下维护子树计数。

  2. 4.2

    选取最小的 k 个记录

    以排名阈值选出恰好 k 个记录,明确订立平手、次序和成本。

第 5 章 · 2 节

哈希

拉链法与碰撞的期望成本。

定理 3 · 定义 5反例 2视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 5.1

    拉链法与碰撞的期望成本

    跟踪拉链查询,并在逐对碰撞假设下证明期望界。

  2. 5.2

    线性探测与墓碑删除

    追踪有界探测并证明删除与键唯一性的不变量。

第 6 章 · 1 节

概率式成员判定

布隆过滤器、保证及假阳性模型。

定理 2 · 定义 1反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 6.1

    布隆过滤器与假阳性

    区分确定性成员保证与理想化假阳性模型。

第 7 章 · 2 节

字符串 Trie

精确成员、前缀列举与安全剪枝。

定理 4 · 定义 2反例 2视角 2证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 7.1

    Trie 前缀、终止标记与安全剪枝

    维护精确字符串成员与前缀列举,并证明删除保留共用路径。

  2. 7.2

    追踪精确查找与前缀补全

    逐字追踪 trie 查询,区分到达节点与已存储键值。

第 8 章 · 1 节

多路搜索树

在插入时保持 B 树的占用和搜索不变量。

定理 3 · 定义 1反例 2视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 8.1

    B 树:不变量、分裂与自顶向下插入

    定义多路搜索树的规格,证明子节点分裂及插入正确,追踪二阶例子,并区分高度、比较及块访问成本。

第 9 章 · 1 节

自调整搜索树

伸展旋转与摊还访问证明。

定理 3 · 定义 2反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 9.1

    伸展树:旋转与访问引理

    追踪伸展操作并证明无权摊还访问界。

第 10 章 · 2 节

链表不变量

哨兵环、节点所属关系与拼接的代价。

定理 3 · 定义 2反例 3视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 10.1

    哨兵链表与节点拼接

    从局部链接推导整体成员关系,并计算查找与维护大小的代价。

  2. 10.2

    递归删除与返回的表头

    追踪节点所有权与元数据,证明递归删除的契约。

第 11 章 · 1 节

动态数组

几何扩缩容与摊还成本。

定理 2 · 定义 1反例 2视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 11.1

    动态数组与摊还成本

    追踪扩缩容并证明摊还更新界。

第 12 章 · 1 节

有序数组搜索

边界搜索与循环不变量。

定理 3 · 定义 1反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 12.1

    二分查找:边界与循环不变量

    证明上下界,处理重复值并分析访问成本。

第 13 章 · 2 节

图遍历

用队列和发现标记寻找无权图最短路径。

定理 5 · 定义 3反例 4视角 2证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 13.1

    广度优先搜索:队列与最短路径

    追踪入队标记,证明层次不变量并重建无权图最短路径。

  2. 13.2

    图的表示与深度优先搜索

    比较邻接矩阵与邻接表,并分析深度优先搜索:时间戳、边的分类、环检测与拓扑序。

第 14 章 · 2 节

图算法

最小生成森林与并查集。

定理 7 · 定义 4反例 3视角 2证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 14.1

    Kruskal 算法:并查集与最小生成森林

    证明森林不变量和贪心割交换,并追踪按大小合并。

  2. 14.2

    加权图的前沿:Dijkstra 与 Prim

    在同一加权图上追踪使用惰性堆的 Dijkstra 算法及 Prim 算法,并证明各自选取步骤的安全性。

第 15 章 · 2 节

平衡搜索树

AVL 树与红黑树:高度界及更新后的修复。

定理 5 · 定义 2反例 2证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 15.1

    AVL 树:高度、旋转与删除

    证明对数高度界,用旋转保持搜索顺序,并逐步分析插入和沿祖先路径传播的删除修复。

  2. 15.2

    红黑树:黑高度与插入修复

    从颜色不变量推导对数搜索深度,证明各种插入修复,并分清重新着色与旋转的代价。

第 16 章 · 1 节

哈希表与通用哈希

链地址法、期望链长与通用哈希族。

定理 2 · 定义 2反例 2证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 16.1

    哈希表:链地址法、通用哈希与期望成本

    在碰撞中保持映射,用指示变量证明期望链长,并用素数模运算构造通用哈希族。

第 17 章 · 1 节

二叉搜索树

普通二叉搜索树的次序不变量与删除。

定理 2 · 定义 1反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 17.1

    二叉搜索树删除:后继、子树返回与节点身份

    以后继节点替换法删除二叉搜索树的键,返回新的子树根,并检验次序不变量与代价。

第 18 章 · 2 节

排序

链表上的归并排序、数组归并排序、快速排序与比较排序下界。

定理 5 · 定义 4反例 2视角 2证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 18.1

    链表上的归并排序:正确性也关乎链接

    以破坏性且稳定的方式合并有序链表,用快慢指针分割链表,并分析链表上的归并排序。

  2. 18.2

    比较排序:归并排序、快速排序与下界

    用不变量与递推式分析数组上的归并排序和快速排序,并证明任何比较排序都需要约 n log n 次比较。

第 19 章 · 1 节

算法分析

代价模型与渐近记号。

定理 2 · 定义 2反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 19.1

    渐近记号与代价模型

    固定代价模型,以明确的常数定义 O、Omega 与 Theta,并推导简单循环代码的增长类别。

Vercel 访问统计与公开页面性能测量分别征求同意,均非使用网站的必要条件。

网站功能存储(按需使用)

安全、登录和你选择的偏好会按需使用存储,与可选统计分开处理。

撤回会停止后续统计;需要卸载已加载的统计程序时,页面会刷新。已发送的数据不会因此删除。

查看 Cookie 与存储详情