课程动态示意图系统设计草稿

这个文件是后续章节绘图系统的技术和教学设计草稿，不进入学生版 PPT。

结论先行

推荐采用“轻量自研 SVG/HTML 组件 + G6 图结构组件”的混合路线。

  • 数组、表格、栈、队列、哈希桶、排序条形图、堆数组视图：使用自研 SVG/HTML 组件。
  • 树、一般图、DAG、最短路、最小生成树、拓扑排序、网络流、复杂关系图：优先使用 G6。
  • D3 作为底层补充能力保留，但不作为统一框架。
  • Cytoscape.js 暂不作为主路线，除非后续要做很大规模网络、复杂图查询或生物网络式交互。

理由：数据结构课程里大量图不是“任意 graph visualization”，而是“教学过程图”。数组、表格、桶、指针、探测路径和排序过程需要像板书一样精准可控；强行塞进 G6 的 node-edge 数据模型，会增加无意义复杂度。G6 应该用在它真正擅长的树和图上。

调研判断

G6 当前文档显示它是 graph visualization engine，提供 graph drawing、layout、analysis、interaction、animation 等能力，并且有节点、边、combo、shape、layout、behavior、plugin、theme、animation 等模块。文档列出多种布局，包括 dagre、circular、force、grid、compact tree、dendrogram、mindmap、radial 等，适合树和图章节。

D3 的优势是底层通用、表达力强，适合自定义坐标、transition、scale 和数据绑定；缺点是需要自己建立完整组件体系，教学图规模一大容易变成“每页手搓”。

Cytoscape.js 是成熟的 graph theory/network visualization library，有布局、选择器、样式表、图算法和动画；它更偏网络应用和图分析系统，不太适合作为课程所有示意图的统一视觉底座。

参考：

  • G6 Introduction: https://g6.antv.antgroup.com/en/manual/introduction
  • G6 Layout Overview: https://g6.antv.antgroup.com/en/manual/layout/overview
  • D3: https://d3js.org/
  • Cytoscape.js: https://js.cytoscape.org/

分层架构

1. QMD 层

QMD 只负责声明“这里需要一个什么演示”，不直接写 SVG/HTML 细节。

示例：

::: {.viz-demo data-viz="array-access" data-values="10,24,17,31" data-target="24"}
:::

或：

::: {.viz-demo data-viz="graph-bfs" data-graph="bfs-example-1" data-start="A"}
:::

2. 组件调度层

建议新增：

  • scripts/course-viz.js
  • scripts/course-viz-g6.js
  • styles/course-viz.css

其中：

  • course-viz.js：通用自研 SVG/HTML 组件，包含数组、表格、栈队列、排序、桶、指针、状态机。
  • course-viz-g6.js：只封装 G6 相关树/图组件，不污染基础组件。
  • course-viz.css：只放语义 token 和通用布局，不为每个具体页面单独写 CSS。

3. 渲染层

每个组件暴露统一接口：

render(root, data, options)
setStep(index)
next()
prev()
run()
final()
reset()
destroy()

不要让每个组件自己发明按钮逻辑。按钮、状态栏、计算栏、说明栏统一由 shell 提供。

4. 状态模型

每个动画都抽象成 step 序列：

{
  task: "insert",
  title: "插入 24",
  highlights: [{ kind: "cell", id: "a[3]", role: "current" }],
  arrows: [{ from: "probe-1", to: "bucket-3", label: "1" }],
  formulas: ["H(24)=3", "bucket 3 occupied"],
  note: "发生碰撞，继续探测下一个位置"
}

这样 Prev/Next/Run/Final/Reset 都只是在 step 上移动，不再由每个动画临时写散乱逻辑。

视觉 token

颜色要少，语义要固定：

  • --viz-ink: 主文字和边框，黑色。
  • --viz-paper: 背景，白色。
  • --viz-muted: 次要线条和标签。
  • --viz-active: 当前步骤，蓝色。
  • --viz-success: 命中或完成。
  • --viz-warning: 冲突、待处理。
  • --viz-danger: 错误、失败、删除。
  • --viz-ghost: 已访问但不是当前。

形状语义：

  • cell：数组格、桶、表格单元。数组、二维数组和开放寻址哈希表必须渲染为连续表格，不使用分离的圆角矩形。
  • token：仅用于链式结构中的链表节点、指针图节点或明确表示对象的场景。开放寻址哈希表中的元素不再使用 token。
  • pointer：指针或引用。
  • edge：树边、图边、链表边。
  • badge：顺序编号、状态标签。
  • formula：计算过程。
  • note：一句解释。

CSS 不按章节或具体图命名，尽量按用途命名。例如：

  • .viz-shell
  • .viz-toolbar
  • .viz-canvas
  • .viz-calc
  • .viz-note
  • .viz-cell
  • .viz-token
  • .viz-edge
  • .viz-pointer
  • .viz-state-active
  • .viz-state-success

尺寸策略

每个组件必须支持三种密度：

  • normal：默认课堂演示，一页一个核心图。
  • compact：配合代码或文字讲解，小图但仍可读。
  • dense：习题答案或多图对比，只用于静态或少量动画。

每个组件必须支持容器自适应：

  • 读取 root 宽高。
  • 根据元素数量计算 cell size / node radius / gap。
  • 超过阈值时优先缩小 gap，其次缩小 cell，最后切换为滚动或分页。
  • 禁止默认把文字压成竖排或让箭头被裁切。

建议基础尺寸：

  • cell 最小宽度：36px。
  • cell 推荐宽度：52px。
  • node 最小直径：34px。
  • node 推荐直径：46px。
  • label 最小字号：12px。
  • 课堂演示字号：14px 到 18px。

自研组件清单

第一阶段必须完成：

  • ArrayView：一维数组、索引、比较顺序、当前元素、区间高亮。
  • TableView：二维表、动态规划表、邻接矩阵、状态转移高亮。
  • BucketTableView：哈希桶、链地址、开放寻址、探测顺序。
  • LinkedListView：单链表、双链表、指针移动、插入删除。
  • StackQueueView：栈、队列、循环队列、双端队列。
  • SortBarsView：排序条形图、比较、交换、已排序区间。
  • FormulaTraceView：计算式逐步展开，与图同步。

第二阶段：

  • HeapArrayView：堆的数组视图。
  • HeapTreeView：堆的树视图，可与数组联动。
  • UnionFindView：森林、parent 数组、路径压缩。
  • MemoryPointerView：对象、地址、引用、空指针。
  • ComplexityCurveView：复杂度曲线、数量级对比。

G6 组件清单

第一阶段：

  • TreeViewG6：普通树、二叉树、遍历、高亮路径。
  • GraphViewG6：无向图/有向图、邻接关系、选边、访问状态。
  • TraversalViewG6：BFS/DFS 队列或栈与图同步。
  • ShortestPathViewG6：Dijkstra/Bellman-Ford 的 dist 表与图同步。
  • MSTViewG6：Kruskal/Prim 的候选边、已选边、环检测。

第二阶段：

  • DAGViewG6：拓扑排序、关键路径。
  • NetworkFlowViewG6：容量、流量、残量网络。
  • GraphAlgorithmCompareG6：同一图上的不同算法过程对比。

G6 只作为树/图渲染引擎，课程层仍然用我们的 step 状态机控制动画。不要把教学逻辑写进 G6 配置里。

标准模板页清单

后续要先做一个 visual-templates.qmd，作为全课程绘图质量基准。至少包含：

  1. 数组查找模板：顺序查找、二分查找，同一数据同一目标。
  2. 排序模板：比较、交换、已排序区间、pivot。
  3. 栈队列模板：push/pop/enqueue/dequeue 的状态变化。
  4. 链表模板：插入、删除、指针重连。
  5. 哈希桶模板：插入、查找、碰撞、探测序列。
  6. 表格模板：动态规划表、当前状态、依赖箭头。
  7. 二叉树模板：插入、查找、旋转、遍历序列。
  8. 堆模板：数组和树联动、上滤/下滤。
  9. 并查集模板：parent 数组和森林联动、路径压缩。
  10. 图遍历模板：BFS/DFS，图与队列/栈联动。
  11. 最短路模板：图、dist 表、visited 集合、当前 relax。
  12. 最小生成树模板：候选边排序、选边、跳过成环。
  13. 复杂度模板：曲线对比、增长数量级、输入规模滑动。

每个模板必须同时验证：

  • 普通尺寸能独立讲一页。
  • compact 尺寸能和代码并排。
  • dense 尺寸能用于习题答案或算法对比。
  • 所有动画都有 Prev/Next/Run/Final/Reset。
  • 计算结果在固定区域展示，不造成画面跳动。

质量标准

  • 图必须像教材级黑白线稿，而不是网页 UI 小组件。
  • 每个图要先服务讲解逻辑，再服务美观。
  • 不允许出现箭头被裁切、文字竖排、桶宽不够、公式挤压主体图。
  • 不允许同一种结构在不同章节使用不同视觉语言。
  • 不允许为单个 slide 写一次性 CSS，除非该 slide 是特殊封面或全章路线图。
  • 动画状态必须可复现。随机动画必须有“教学随机”和“固定种子/固定结果”两种模式。
  • 所有核心模板必须能离线打开；若使用 G6，最终要 vendored 到项目资源里，不依赖 CDN。

实施顺序

  1. 新建 scripts/course-viz.js 和 styles/course-viz.css，先抽出已有哈希章节中可复用的 shell、bucket、token、arrow、formula、step runner。
  2. 新建 chapters/00-visual-templates.qmd，只做模板页，不作为正式课程章节。
  3. 先完成自研组件的数组、表格、桶、链表、栈队列、排序条形图。
  4. 再接入 G6，完成树和图的模板。
  5. 每完成一个模板，回填到 chapter-production-guidelines.md 中作为后续章节规则。
  6. 之后再开始迁移第 3、4、6、7、8、9 章，避免每章临时发明图形。

当前决策

  • 不把 G6 用作所有图形的唯一底座。
  • 不继续扩张 hash-demo.js 为全课程大杂烩。
  • 后续应拆出 course-viz，哈希章节逐步迁移到新组件。
  • 标准模板页先做，正式章节后做。先有视觉和交互标准，再批量生产内容。

当前实现状态

  • 已新增 chapters/00-visual-templates.qmd，作为标准组件模板页。
  • 已新增 scripts/course-viz.js，不覆盖原有 hash-demo.js。
  • 已新增 styles/course-viz.css，使用语义化 .viz-* class，避免继续按单页写 CSS。
  • 已新增 scripts/course-viz-include.html，当前通过 CDN 加载 G2、G6、S2、X6；后续定稿后应 vendored 到本地资源。
  • 已实现第一批标准组件：数组查找、动态规划表、哈希桶线性探测、链式哈希、树遍历、AVL 旋转、图 BFS、Dijkstra 最短路联动演示、碰撞统计图、邻接矩阵、链表指针重连、2,4-Cuckoo 插入与删除。
  • G2 用于碰撞统计图。
  • X6 用于数组、DP 表、开放寻址哈希表、链式哈希、邻接矩阵、链表/指针图、树、图、AVL 旋转和 Cuckoo 哈希。
  • 不再实现 fallback。浏览器必须支持所选 AntV 组件；如果组件加载失败，应显式暴露错误，而不是悄悄退化成另一套绘图语言。
  • 第五章现有哈希绘图没有被覆盖，可随时回退。
  • 已按新视觉规则重构第一批模板：动画不使用外框；按钮居中；计算过程用逗号分隔纯文本。
  • 2026-07-16 再次重构：模板页所有绘图均改为 AntV 渲染，不再使用自绘 SVG/HTML table fallback。
  • 一维数组、动态规划表和开放寻址哈希表改为 X6 连续网格，避免 reveal 全局 table CSS 造成格子分离。
  • 树和图暂时改为 X6 固定坐标布局，优先保证节点完整显示；后续若需要自动布局，再单独接 G6。
  • 统计图继续使用 G2；链表/指针图、数组、DP 表、哈希表、邻接矩阵、树和图均使用 X6。
  • 邻接矩阵是图结构的一部分，不使用 S2。S2 只在后续确实需要多维统计表或数据透视表时再引入。
  • 当前 CDN：G2 使用 https://unpkg.com/@antv/g2/dist/g2.min.js，X6 使用 https://unpkg.com/@antv/x6/dist/x6.min.js。最终分发前仍应 vendored 到本地。
  • 2026-07-16 更新：数组下标放在上方，使用无外框细字；数组查找箭头从下往上指向格子。
  • DP 表和邻接矩阵的顶部表头与左侧表头使用不同浅色背景。
  • 开放寻址哈希表只显示纵向连续表格和左侧无框下标；不再出现 bucket X 文本，也不再用左侧箭头格。
  • 链式哈希新增标准模板：桶本身是纵向连续表格，链表节点在桶外按链表格式用 X6 节点和箭头连接。
  • 搜索/遍历统一标注：visited 为灰色，当前访问为蓝色。数字+箭头只用于数组查找和哈希表探测/定位，不用于 DP、矩阵、树或图。
  • 查找/插入开始前，在结构左侧放置黄色高亮的待查/待插入 key。
  • 数字顺序标号只作为辅助线索，必须小而轻，不抢占主体视觉。
  • 动态规划和矩阵更新的依赖来源使用浅绿色，不使用 visited 灰色；不要画依赖箭头，避免遮挡格子内容。
  • 树遍历需要在树边上画访问/回溯箭头：蓝色实线箭头表示向子节点访问，灰色虚线箭头表示回溯，不使用独立数字标签。
  • 图遍历不画数字箭头；必须清晰区分当前访问、已经访问和即将访问。当前访问为蓝色，已经访问为更明显的灰色，frontier 为黄色。
  • 学生可见的计算说明和解释尽量使用中文；代码变量名和库内部字段不计入学生说明。

2026-07-16 最新模板修订

  • 链表插入动画必须从“孤立新节点”开始：先保持原链 10 -> 17 -> 31，再画 24.next -> 31，再画 17.next -> 24，最后合并为 10 -> 17 -> 24 -> 31。
  • 链表插入中，24.next -> 31 建立后，旧的 17.next -> 31 仍然是实线；只有执行 17.next = 24 后旧边才消失。
  • AVL 旋转模板使用具体插入序列 A, Z, C, W, D, X, Y，按字典序插入并逐步展示 RL、LL、RR、LR 旋转过程；不能再使用抽象的 x/y/z 瞎转示意。
  • AVL 演示必须使用固定舞台高度，不随节点数量改变视觉高度；底部保留紧凑流程缩略条，顶部先说明当前插入谁，再展示插入路径、失衡点和旋转。颜色语义：蓝色表示当前插入/旋转对象，黄色表示失衡点或旋转支点，蓝边表示插入路径，虚线高度标尺用于帮助学生判断平衡变化。
  • 2,4-Cuckoo 哈希模板中的“2,4”含义是：每个 key 有两个候选 bucket，每个 bucket 有 4 个 slot。它不是两张分开的单槽 cuckoo 表。演示必须画 bucketized table，包含无高亮起始帧、key 出现帧、h_0(key) / h_1(key) 候选箭头、DFS 搜索满桶、cuckoo path、kick 过程和删除只检查两个候选桶。
  • Cuckoo 的 bucket/slot 下标不带框；slot 只写数字，bucket 左侧只写数字。表格上方只写 h_0(·) 与 h_1(·) 表示两个哈希函数，不展开具体算式。
  • Cuckoo 插入要分成两个阶段，而不是相互替代：第一阶段按真实 kick 过程逐步移动 key；第二阶段回到初始表，把同一问题重新解释为图搜索，分别演示 DFS 和 BFS。DFS 可沿一条路径较快命中空位，BFS 会先展开整层候选，体现分支因子带来的搜索规模差异。搜索阶段只决定路径，移动阶段再统一应用路径。
  • Cuckoo 搜索阶段的当前 key 仍然是待插入 key，例如 24；被访问到的 17、6 是路径上的旧 key，不应切换成“当前 key”。已经处于某个候选函数位置的旧 key，要把原函数标灰，把另一个函数标为当前候选，例如 17 从 h₀ 位置被踢出后探测 h₁(17)，6 从 h₁ 位置被踢出后返回 h₀(6)。
  • Cuckoo path 箭头统一使用蓝色，不在箭头上写文字；函数标注放在表格外侧。箭头终点应避开格子文字，不能盖住数字。
  • 开放寻址哈希表的探测序号和箭头必须放在桶下标左侧、整个表格外面；探测过程必须逐桶推进，不允许一帧跳过多个访问位置。
  • Dijkstra 模板使用图与表格双栏联动：图上显示当前确定节点、frontier、松弛边和最短路径树边；表格同步显示 dist / prev / settled，本轮更新的单元使用浅绿色。
  • 全工程默认键盘行为：方向键、PageUp/PageDown、空格默认先驱动当前页动画的 Prev/Next；只有按 Ctrl/Meta 加方向键时才跳过动画、直接交给 reveal 翻页。该行为由 scripts/course-keyboard.js 安装，脚本必须单例保护，避免全局 include 和章节 include 重复加载时重复绑定。
  • 验证标准：chapters/00-visual-templates.qmd 渲染后，页面中所有 data-viz 必须全部生成 viz-shell 和 viz-antv-canvas，且不能出现 Unknown viz 或 SyntaxError。