dsa-yin

name	dsa-yin
description	Knowledge base from "数据结构（用面向对象方法与C++语言描述）第3版" by 殷人昆. Use when learning or applying data structures with C++ and object-oriented design - covers linear structures, stacks, queues, arrays, strings, trees, graphs, sets, dictionaries, search structures, sorting, and external sorting.

数据结构（用面向对象方法与C++语言描述）第3版

Author: 殷人昆 | Pages: ~501 | Chapters: 10 | Generated: 2026-07-08

How to Use This Skill

• Without arguments - load core frameworks below
• With a topic - ask about 红黑树, KMP, Dijkstra, or another indexed topic from the Topic Index
• With chapter - ask for ch07
• Browse - ask "what chapters do you have?" or "topic index"

Core Frameworks & Mental Models

Data Structure Design (Ch1)

• Use ADT (抽象数据类型) when designing any data structure: separate interface (what) from implementation (how). Define private data + public operations; encapsulate via C++ class with private/protected/public.
• Use 顺序存储 when data size is stable, random access dominates, insert/delete is rare. Use 链接存储 when insert/delete is frequent, storage demand is unpredictable.
• Use 大O加法 for sequential blocks: O(max{f, g}). Use 大O乘法 for nested loops: O(f * g). Recursion adds O(depth) stack space — convert tail/one-way recursion to iteration when stack overflow is a risk.

Linear Structures (Ch2-3)

• Use 带附加头结点的链表 for every linked list implementation — eliminates empty vs non-empty branch handling.
• Use 循环链表 when cyclic traversal is needed (Josephus, round-robin). Use 双向链表 when O(1) deletion of an arbitrary known node or bidirectional scan is needed.
• Use LIFO/栈 for: function calls, undo, bracket matching, expression evaluation, backtracking. Use FIFO/队列 for: task scheduling, BFS, I/O buffering, level-order traversal.
• Use 循环队列(rear+1)%maxSize==front to detect fullness — sacrifice one slot to disambiguate from empty (front==rear).
• Use 递归 when problem definition is naturally recursive AND depth is bounded (< thousands). Use 迭代 when recursion causes exponential explosion (e.g., Fib(40) ~3e8 calls) or stack overflow.
• Use 回溯法 for maze solving, N-Queens, DFS — stack remembers the path; "try forward, backtrack on failure."

Arrays, Strings, Generalized Lists (Ch4)

• Use 对称矩阵压缩 for covariance matrices, undirected graph adjacency — store n(n+1)/2 elements instead of n^2.
• Use 三元组数组 for sparse matrix transpose/output (read-heavy). Use 十字链表 when non-zero elements change dynamically during computation.
• Use B-F (朴素匹配) when pattern is short (m<10) or called rarely. Use KMP when pattern is long or matching is frequent — O(n+m), target pointer never backtracks. Core: next[j] = longest equal prefix-suffix length, computed via KMP of P against itself.
• Use 广义表 for recursive nested structures (LISP-style lists, tree serialization). Union-based node (utype=0/1/2) + tagged union pattern.

Trees (Ch5)

• Use 前序 (VLR) for cloning/serialization. Use 中序 (LVR) for BST sorted output. Use 后序 (LRV) for computing subtree aggregate properties (height, size, destruction).
• Use 非递归遍历 (栈) when stack depth from recursion is a concern. Use 层次遍历 (队列) for BFS / level-by-level processing.
• Use 线索二叉树 (中序) when frequent in-order successor/predecessor queries — repurpose n+1 empty child pointers as thread shortcuts. ltag/rtag flags distinguish child vs thread.
• Use 子女-兄弟链表 to convert any tree to a binary tree: firstChild→leftChild, nextSibling→rightChild. Unifies all tree operations under the binary tree framework.
• Use 完全二叉树数组存储 for heaps — parent at ⌊i/2⌋, left child at 2i, right child at 2i+1. Zero pointer overhead.
• Key invariant: n0 = n2 + 1 (leaf count = degree-2 node count + 1). Catalan number C(2n,n)/(n+1) counts distinct binary trees of n nodes (equals stack pop sequences).

Sets, Dictionaries, Hashing (Ch6)

• Use 位向量 when the universal set is small and elements map to consecutive integers — O(1) membership, bitwise union/intersection.
• Use 并查集 (加权合并 + 路径压缩) for dynamic equivalence class management — nearly O(1) amortized per operation. Both Kruskal's MST and equivalence partitioning need it.
• Use 跳表 when you need binary search efficiency on a linked list — average O(log n), simpler than balanced trees, ~2n pointer overhead.
• Use 散列 (开散列/链地址法) as the default dictionary implementation — O(1) average search. Use 除留余数法 with prime divisor for the hash function. Use 闭散列 with 二次探查 only when alpha < 0.5.
• Critical: closed hashing deletion must be logical (tombstone marker), never physical — otherwise search chains break.

Search Structures (Ch7)

• Use 折半搜索 when data is static and sorted in a sequential list — O(log n) comparisons, but O(n) insert/delete.
• Use 二叉搜索树 (BST) for dynamic dictionaries — O(log n) average search with random insertion order. WARNING: sorted insertion order degenerates BST to a linked list O(n).
• Use AVL 树 when strict O(log n) search guarantee is required — height ~1.44log(n+2), at most one rotation per insert. Four rotation cases: LL (single right), RR (single left), LR (left-then-right double), RL (right-then-left double).
• Use 红黑树 when insert/delete is frequent — height ~2log(n+1) but rebalancing work is lighter. Most widely used in practice (C++ std::map, Java TreeMap).
• Use 伸展树 when access pattern has strong locality — recently accessed nodes stay near root, amortized O(log n).

Graphs (Ch8)

• Use 邻接矩阵 for dense graphs (e close to n^2), O(1) edge test. Use 邻接表 for sparse graphs (e << n^2), O(n+e) space, efficient neighbor traversal.
• Use DFS for connectivity, articulation points, topological sort, strongly connected components — recursive natural fit, corresponds to tree pre-order. Use BFS for level-order traversal, unweighted shortest path — queue-based.
• Use Kruskal for sparse MST (sort edges + Union-Find). Use Prim for dense MST (maintain cut set + min-heap).
• Use Dijkstra for single-source shortest paths with non-negative weights — O(n^2), greedy by increasing distance. WARNING: fails on negative edges. Use Bellman-Ford when negative edges exist (no negative cycles). Use Floyd for all-pairs shortest paths — simple triple loop O(n^3).
• Use 拓扑排序 first in any DAG-based scheduling — detects cycles, produces execution order. Use 关键路径 on AOE networks for project scheduling: compute Ve (earliest) forward, Vl (latest) backward, critical activities have zero slack.

Sorting (Ch9)

• Use 直接插入排序 when n <= 25 or data is nearly sorted — O(n) best case.
• Use 希尔排序 when n is moderate (<= 1000) — code is simple, ~O(n^1.25), no extra space.
• Use 快速排序 as the default general-purpose sort — O(n log n) average, fastest in practice. MUST use median-of-three pivot + switch to insertion sort for small subarrays (n <= 25). Without these, sorted input degenerates to O(n^2).
• Use 堆排序 when O(n log n) worst-case guarantee is required AND O(1) extra space — slower average than quicksort but no degradation.
• Use 归并排序 when stable O(n log n) sort is required — needs O(n) extra space; linked-list version avoids element moves.
• Use 基数排序 (LSD) when sort key decomposes into d digits with moderate radix — O(d*(n+radix)), linear time but high constant.
• Fundamental lower bound: comparison-based sorting is Omega(n log n), proven via decision tree with n! leaves.

External Structures (Ch10)

• Use k路归并 + 败者树 for external sorting — loser tree picks min among k runs in O(log k) comparisons (independent of k). Merge passes S = ceil(log_k m).
• Use 置换-选择排序 to generate initial runs ~2x memory workspace size, reducing m and thus merge passes.
• Use B树 (m-way) as the standard external index — height h <= log_{ceil(m/2)}((N+1)/2) + 1. A 200-order B-tree with h=4 indexes ~16B keys. Use B+树 when range scans are needed — all keys reside in linked leaf layer.
• Use 散列文件 for fast direct access by key. Use 倒排文件 for multi-attribute queries.

Chapter Index

#	Title	Key Frameworks
1	数据结构概论	ADT, 四种存储方法, 大O分析, 程序步计数, 选择数据结构三步法
2	线性表	顺序表 vs 链表, 附加头结点, 循环/双向链表, 静态链表, 多项式加法
3	栈和队列	LIFO/FIFO, 中缀→后缀转换 (isp/icp), 递归三要素, 回溯法, 循环队列, 优先级队列
4	数组、串与广义表	多维数组行优先映射, 对称/三对角/稀疏矩阵压缩, KMP 无回溯匹配, 广义表 union 结点
5	树	二叉树五大性质, 前/中/后/层次遍历(递归+非递归), 线索二叉树, Catalan 计数, 子女-兄弟表示
6	集合与字典	位向量, 并查集(加权合并+路径压缩), 跳表, 散列(闭散列/开散列), 装载因子控制
7	搜索结构	顺序/折半搜索, BST, AVL 四种旋转, 伸展树, 红黑树, 斐波那契搜索
8	图	邻接矩阵/表/多重表, DFS/BFS, Kruskal/Prim, Dijkstra/Bellman-Ford/Floyd, 拓扑排序, 关键路径
9	排序	插入/希尔/快速/堆/归并/基数排序, 三者取中优化, 排序下界 Omega(n log n)
10	文件、外部排序与搜索	顺序/散列/索引/倒排文件, k路归并+败者树, 置换-选择, B树/B+树, Trie/双链树

Topic Index

Topic	Ch		Topic	Ch
ADT 抽象数据类型	1		邻接矩阵 / 邻接表	8
AVL 树 (四种旋转)	7		判定树	7
B 树 / B+ 树	10		排序下界 (Omega n log n)	9
Bellman-Ford 算法	8		平衡因子 (bf)	7
Catalan 数 (二叉树计数)	5		前序/中序/后序/层次遍历	5
Dijkstra 最短路径	8		起泡排序	9
Floyd 全源最短路径	8		前缀/中缀/后缀表达式	3
KMP 模式匹配 (next数组)	4		嵌套循环时间复杂度	1
Kruskal / Prim MST	8		散列表 (闭散列/开散列)	6
LSD 基数排序	9		伸展树 (Splay Tree)	7
Trie 树 / 双链树	10		十字链表 (稀疏矩阵)	4
败者树 (Loser Tree)	10		数据结构 = {D, R}	1
并查集 (加权合并+路径压缩)	6		数组行优先存储映射	4
插入排序 / 折半插入	9		跳表	6
成员函数 const / this	2		拓扑排序 / AOV 网络	8
递归工作栈 / 递归→迭代	3		线索二叉树	5
堆排序 (最大堆)	9		循环队列 (假溢出)	3
对称矩阵压缩存储	4		循环链表 / 双向链表	2
二叉搜索树 (BST)	7		优先级队列	3
二叉树性质 (n0=n2+1)	5		折半搜索	7
二叉树由前序+中序构造	5		置换-选择排序	10
附加头结点 (链表)	2		子女-兄弟链表 (树→二叉树)	5
归并排序 / k路归并	9/10		装载因子 (alpha)	6
广义表	4		监视哨 (Sentinel)	7
红黑树	7		字符串 (B-F vs KMP)	4
回溯法 (迷宫, N皇后)	3		关键路径 (AOE 网络)	8
快速排序 (三者取中)	9

Supporting Files

• glossary.md — every significant term, alphabetically categorized
• patterns.md — reusable algorithm patterns with when/how/trade-offs
• cheatsheet.md — decision matrices, thresholds, selection guides

Scope & Limits

This skill covers the book content only. All code examples are in C++. For Python DSA, see dsa-hello-algo. For complementary C++ DSA theory, see dsa-deng (邓俊辉).