你的进度
0/ 14 节已标记完成
下一节: 0.1 指针、内存与结构体
完成记录保存在此浏览器中。
这门课在网上
CSCI2520 笔记里的内容
数字只算这门课 14 节公开笔记里写了什么，不是网上已记录的关系。目前其中 0 节已细致地记录到网上。
在网上定理卡 34 · 定义 47
第 0 章 · 1 节
程序基础
数据结构笔记会反复用到的语言与内存工具。
- 0.1
指针、内存与结构体
重温课程用来解释数据结构行为的 C 语言工具：指针、malloc 动态分配、typedef 类型别名与 struct 结构体布局。
第 1 章 · 2 节
ADT 与操作语义
由 ADT 规格走向 stack/queue 行为，再进入 dictionary 形式的 hashing 操作。
- 1.1
ADT 操作：栈、队列与函数指针
以抽象数据类型（ADT）的角度精确理解栈、队列，以及 C 语言中以函数指针进行操作分派的设计。
- 1.2
哈希表与碰撞处理策略
用字典操作、哈希函数、冲突与链地址法去理解哈希表为何以有序结构换取平均情况下的快速存取。
第 2 章 · 1 节
列表与递归
递归 list 契约、head-tail 推理，以及受 representation 影响的操作成本。
- 2.1
作为递归 ADT 的列表
把列表读成递归的头尾（head-tail）抽象数据类型，再比较迭代与递归两种操作实现。
第 3 章 · 2 节
复杂度与排序
渐进增长、成本比较与面向排序的复杂度推理。
- 3.1
复杂度增长与算法成本
在实作排序或选择算法前，先解读渐进增长并比较成本。
- 3.2
选择问题、快速选择与线性时间排序
分清选择与完整排序，再用快速选择、计数排序、基数排序理解额外结构何时改善复杂度。
第 4 章 · 2 节
树与二叉搜索树
Binary tree traversal、reconstruction 与 binary-search-tree operations。
- 4.1
二叉树遍历与重建
通过前序、中序与后序遍历理解二叉树的递归结构，再由充分的遍历信息重建树。
- 4.2
二叉搜索树与核心操作
在搜索、极值、插入、后继与删除操作中维持二叉搜索树的排序不变式，并以树高分析成本。
第 5 章 · 4 节
图
Graph representation 与 traversal、minimum spanning tree、shortest path 及 topological ordering。
- 5.1
图的表示、深度优先搜索与广度优先搜索
比较邻接矩阵与邻接表，再以正确的边界与已访问状态不变式追踪深度优先搜索（DFS）与广度优先搜索（BFS）。
- 5.2
最小生成树：Prim 与 Kruskal
以 Prim 与 Kruskal 的贪心选择构造最小生成树，并分清最小生成树的目标与最短路径。
- 5.3
最短路径与 Dijkstra 算法
在边权非负的前提下，用松弛与已确定顶点的推理，以 Dijkstra 算法计算单源最短路径。
- 5.4
有向无环图的拓扑排序
以 Kahn 入度流程与 DFS 完成时间排列有向无环图（DAG）的顶点，并由两种方法识别有向环。
第 6 章 · 2 节
堆与贪心编码
Binary heap、priority queue、Huffman coding 与以 heap 实现的 multiway merging。
- 6.1
二叉堆与优先队列
以数组表示完全二叉树，并通过优先队列操作及自底向上建堆维持最小堆的次序。
- 6.2
Huffman 编码与堆的应用
以反复合并最低频率构造无前缀的 Huffman 编码，再把堆的抽象用于高效的多路合并。