CSCI2520：资料结构

资料结构笔记。

0.1 Pointer、内存与 struct

浏览章节

章节 0

程序基础

资料结构笔记会反复用到的语言与内存工具。

0.1 Pointer、内存与 struct
重温课程用来解释资料结构行为的 C 语言工具：pointer、malloc、typedef 与 struct 布局。
阅读本节

章节 1

由 ADT 规格走向 stack/queue 行为，再进入 dictionary 形式的 hashing 操作。

1.1 ADT 操作：stack、queue 与 function pointer
以 ADT 角度精确理解 stack、queue 以及 C 语言中以 function pointer 进行操作分派的设计。
阅读本节
1.2 Hash table 与 collision 策略
用 dictionary 操作、hash function、collision 与 chaining 去理解 hash table 为何以有序结构换取平均情况下的快速存取。
阅读本节

章节 2

递归 list 契约、head-tail 推理，以及受 representation 影响的操作成本。

2.1 作为递归 ADT 的 list
把 list 读成递归的 head-tail ADT，再比较 iterative 与 recursive 操作实作。
阅读本节

章节 3

渐进增长、成本比较与面向排序的复杂度推理。

3.1 复杂度增长与算法成本
在实作排序或选择算法前，先解读渐进增长并比较成本。
阅读本节
3.2 Selection、quickselect 与 linear-time sorting
分清 selection 与完整 sorting，再用 quickselect、counting sort、radix sort 理解额外结构何时改善复杂度。
阅读本节

章节 4

Binary tree traversal、reconstruction 与 binary-search-tree operations。

4.1 Binary tree traversal 与重建
通过 preorder、inorder 与 postorder traversal 理解 binary tree 的递归结构，再由充分的 traversal 信息重建树。
阅读本节
4.2 Binary search tree 与核心操作
在 search、extrema、insertion、successor 与 deletion 中维持 binary-search-tree ordering invariant，并以树高分析成本。
阅读本节

章节 5

Graph representation 与 traversal、minimum spanning tree、shortest path 及 topological ordering。

5.1 Graph representation、DFS 与 BFS
比较 adjacency matrix 与 adjacency list，再以正确的 frontier 及 visited-state invariant 追踪 DFS 与 BFS。
阅读本节
5.2 Minimum spanning tree：Prim 与 Kruskal
以 Prim 与 Kruskal 的 greedy choice 构造 minimum spanning tree，并分清 MST objective 与 shortest path。
阅读本节
5.3 Shortest path 与 Dijkstra algorithm
在非负 edge weight 前提下，用 relaxation 与 settled-vertex reasoning 以 Dijkstra algorithm 计算 single-source shortest path。
阅读本节
5.4 DAG 的 topological sorting
以 Kahn indegree process 与 DFS finishing time 排列 DAG vertices，并由两种方法识别 directed cycle。
阅读本节

章节 6

Binary heap、priority queue、Huffman coding 与以 heap 实现的 multiway merging。

6.1 Binary heap 与 priority queue
以 array 表示 complete binary tree，并通过 priority-queue operations 及 bottom-up construction 维持 min-heap order。
阅读本节
6.2 Huffman coding 与 heap 应用
以反复合并最低 frequency 构造 prefix-free Huffman code，再把 heap abstraction 用于高效 multiway merging。
阅读本节