跳转至

全书总索引系统

1. 使用说明

这份索引的目标不是重复各章正文，而是解决四类“像翻教材附录一样”的需求：

  1. 忘了一个术语在哪一章讲过
  2. 忘了一个公式该去哪里查
  3. 忘了一个代码函数在哪个文件里
  4. 想把增强版内容和原 PDF 页码快速对齐

最推荐的配合方式：

  1. 先从站点首页、目录页或附录导航进入整套材料
  2. 系统复习时配合本书附录中的总复习路线图
  3. 精确回查术语、公式和函数时优先使用这份总索引

2. 原 PDF 页码映射总表

原 PDF 页码 对应章节 当前主文件
13-23 第1章 绪论 本书第1章正文
24-73 第2章 线性表 本书第2章正文
74-120 第3章 栈、队列和数组 本书第3章正文
121-135 第4章 串 本书第4章正文
136-209 第5章 树与二叉树 本书第5章正文
210-280 第6章 图 本书第6章正文
281-348 第7章 查找 本书第7章正文
349-411 第8章 排序 本书第8章正文

补充说明：

  1. 每章都保留了对应的 OCR 底稿、构建脚本和示例程序，主要用于工程维护和内容校对。
  2. 面向日常阅读时，优先使用正文页、代码专题页和本附录中的索引入口即可。

3. 术语总索引

3.1 第1章 绪论

核心术语：

  1. 数据结构
  2. 逻辑结构
  3. 存储结构
  4. 数据运算
  5. 算法五特性
  6. 时间复杂度
  7. 空间复杂度
  8. 最好 / 平均 / 最坏情况

主入口：

  1. 本书第1章正文

3.2 第2章 线性表

核心术语：

  1. 顺序表
  2. 动态顺序表
  3. 单链表
  4. 双链表
  5. 循环链表
  6. 静态链表
  7. 头插法
  8. 尾插法
  9. 头结点
  10. 按位查找
  11. 按值查找
  12. 链表逆置

主入口：

  1. 本书第2章正文
  2. 第2章普通代码版

3.3 第3章 栈、队列和数组

核心术语：

  1. 栈
  2. 顺序栈
  3. 链栈
  4. 共享栈
  5. 队列
  6. 顺序队列
  7. 假溢出
  8. 循环队列
  9. 链队列
  10. 双端队列
  11. 后缀表达式
  12. 行优先存储
  13. 列优先存储
  14. 稀疏矩阵
  15. 三元组表

主入口：

  1. 本书第3章正文
  2. 第3章普通代码版

3.4 第4章 串

核心术语：

  1. 串
  2. 子串
  3. 主串
  4. 模式串
  5. BF 匹配
  6. KMP
  7. next 数组
  8. nextval 数组
  9. 匹配失败跳转
  10. 可重叠匹配

主入口：

  1. 本书第4章正文
  2. 第4章普通代码版

3.5 第5章 树与二叉树

核心术语：

  1. 树
  2. 结点度
  3. 树高
  4. 二叉树
  5. 满二叉树
  6. 完全二叉树
  7. 先序 / 中序 / 后序 / 层序遍历
  8. 线索二叉树
  9. 左孩子右兄弟
  10. 森林
  11. 哈夫曼树
  12. WPL
  13. 并查集

主入口：

  1. 本书第5章正文
  2. 第5章普通代码版

3.6 第6章 图

核心术语：

  1. 无向图
  2. 有向图
  3. 度 / 入度 / 出度
  4. 路径 / 回路
  5. 连通分量
  6. 强连通分量
  7. 邻接矩阵
  8. 邻接表
  9. DFS
  10. BFS
  11. 拓扑排序
  12. 最小生成树
  13. Prim
  14. Kruskal
  15. Dijkstra
  16. Floyd
  17. AOE 网
  18. 关键路径
  19. 关键活动

主入口：

  1. 本书第6章正文
  2. 第6章普通代码版

3.7 第7章 查找

核心术语：

  1. 查找表
  2. 静态查找
  3. 动态查找
  4. ASL
  5. 顺序查找
  6. 折半查找
  7. 分块查找
  8. 判定树
  9. BST
  10. AVL
  11. 红黑树
  12. B 树
  13. B+ 树
  14. Hash 表
  15. 装填因子
  16. 开放定址法
  17. 拉链法
  18. 堆积
  19. 逻辑删除

主入口：

  1. 本书第7章正文
  2. 第7章普通代码版

3.8 第8章 排序

核心术语：

  1. 稳定性
  2. 内部排序
  3. 外部排序
  4. 插入排序
  5. 冒泡排序
  6. 快速排序
  7. 选择排序
  8. 堆排序
  9. 归并排序
  10. 计数排序
  11. 基数排序
  12. 初始归并段
  13. 多路归并
  14. 败者树
  15. 置换-选择

主入口：

  1. 本书第8章正文
  2. 第8章普通代码版

4. 公式总索引

4.1 复杂度基础

  1. 顺序查找成功 ASL = (n + 1) / 2
  2. 无序顺序表顺序查找失败 ASL = n
  3. 折半查找平均时间复杂度 O(log n)
  4. Hash 表装填因子 alpha = n / m

主入口：

  1. 本书第1章正文
  2. 本书第7章正文

4.2 数组与矩阵地址公式

  1. 一维数组偏移：Loc(a[i]) = Loc(a[low]) + (i - low) * L
  2. 二维数组行优先：Loc(a[i][j]) = base + ((i - row_low) * col_count + (j - col_low)) * L
  3. 二维数组列优先：Loc(a[i][j]) = base + ((j - col_low) * row_count + (i - row_low)) * L
  4. 对称矩阵压缩、三角矩阵压缩、三对角矩阵压缩的映射公式

主入口：

  1. 本书第3章正文
  2. 第3章普通代码版

4.3 二叉树与树

  1. 二叉树性质：n0 = n2 + 1
  2. 满二叉树结点数：2^h - 1
  3. 第 i 层最多结点数：2^(i-1)
  4. 哈夫曼树带权路径长度：WPL = sum(wi * li)

主入口：

  1. 本书第5章正文
  2. 第5章普通代码版

4.4 图论高频公式

  1. 无向图度数和：sum(deg(v)) = 2e
  2. 有向图：sum(indegree) = sum(outdegree) = e
  3. 连通无向图最少边数：n - 1
  4. 强连通有向图最少边数：n（通常指 n > 1）
  5. Floyd 递推：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
  6. 关键路径参数：ve、vl、ee、el、l = el - ee

主入口：

  1. 本书第6章正文
  2. 第6章普通代码版

4.5 查找与多路平衡树

  1. 折半查找判定树深度与比较次数对应
  2. B 树结点关键字数范围：[t-1, 2t-1]
  3. B 树孩子数范围：[t, 2t]（非根内部结点）

主入口：

  1. 本书第7章正文
  2. 第7章普通代码版

4.6 排序比较公式与性质

  1. 直接插入 / 冒泡 / 选择的最坏时间复杂度通常为 O(n^2)
  2. 快速排序平均时间复杂度 O(n log n)，最坏 O(n^2)
  3. 堆排序时间复杂度 O(n log n)
  4. 归并排序时间复杂度 O(n log n)，辅助空间 O(n)
  5. 计数排序、基数排序不属于比较型排序
  6. 外部排序归并趟数由“初始归并段个数 + 归并路数”共同决定

主入口：

  1. 本书第8章正文
  2. 第8章普通代码版

5. 代码函数总索引

5.1 第2章 线性表

代码主入口：第2章普通代码版

顺序表：

  1. InitSeqList
  2. DestroySeqList
  3. EnsureSeqListCapacity
  4. SeqListInsert
  5. SeqListDelete
  6. SeqListGetElem
  7. SeqListLocateElem
  8. SeqListEmpty
  9. SeqListLength
  10. PrintSeqList

单链表：

  1. InitLinkList
  2. DestroyLinkList
  3. LinkListLength
  4. LinkListGetElem
  5. LinkListLocateElem
  6. LinkListInsert
  7. LinkListDelete
  8. BuildLinkListHeadInsert
  9. BuildLinkListTailInsert
  10. ReverseLinkList
  11. PrintLinkList

双链表 / 循环链表 / 静态链表：

  1. InitDLinkList
  2. DestroyDLinkList
  3. DLinkListPushBack
  4. DLinkListInsertAfter
  5. DLinkListDeleteNode
  6. PrintDLinkList
  7. InitCircularList
  8. DestroyCircularList
  9. CircularListPushBack
  10. PrintCircularList
  11. InitStaticLinkList
  12. StaticAlloc
  13. StaticFree
  14. StaticPushFront
  15. PrintStaticLinkList

综合题函数：

  1. FindKthFromEnd
  2. PrintPairsWithSum
  3. IsDLinkListSymmetric
  4. FindFirstCommonNode
  5. RemoveAbsDuplicates
  6. ReorderListFrontBack
  7. RemoveRangeSeqList
  8. DeduplicateSortedSeqList
  9. MergeSortedSeqLists
  10. MergeSortedLinkLists
  11. PartitionLinkListByValue
  12. DeleteMinSeqList
  13. ReverseSeqList
  14. DeduplicateSortedLinkList
  15. FindMiddleNode
  16. IntersectSortedLinkLists
  17. FindLoopStartNode
  18. JoinCircularLists
  19. PairSumLinkList

5.2 第3章 栈、队列和数组

代码主入口：第3章普通代码版

栈：

  1. InitSeqStack
  2. SeqStackEmpty
  3. SeqStackFull
  4. PushSeqStack
  5. PopSeqStack
  6. GetTopSeqStack
  7. PrintSeqStack
  8. InitSharedStack
  9. PushSharedStack0
  10. PushSharedStack1
  11. PopSharedStack0
  12. PopSharedStack1
  13. InitLinkStack
  14. PushLinkStack
  15. PopLinkStack
  16. GetTopLinkStack
  17. DestroyLinkStack

应用：

  1. IsBracketSequenceBalanced
  2. OperatorPrecedence
  3. ApplyBinaryOperator
  4. EvaluatePostfixExpression

数组与矩阵：

  1. RowMajorIndex1D
  2. RowMajorIndex2D
  3. ColMajorIndex2D
  4. SymmetricMatrixIndex
  5. LowerTriangularMatrixIndex
  6. UpperTriangularMatrixIndex
  7. TridiagonalMatrixIndex
  8. DenseMatrixToTriples
  9. PrintTriples

队列与双端队列：

  1. InitCircularQueue
  2. EnqueueCircularQueue
  3. DequeueCircularQueue
  4. GetHeadCircularQueue
  5. PrintCircularQueue
  6. InitLinkQueue
  7. EnqueueLinkQueue
  8. DequeueLinkQueue
  9. GetHeadLinkQueue
  10. PrintLinkQueue
  11. DestroyLinkQueue
  12. InitDeque
  13. PushFrontDeque
  14. PushBackDeque
  15. PopFrontDeque
  16. PopBackDeque
  17. PrintDeque

5.3 第4章 串

代码主入口：第4章普通代码版

顺序串 / 堆串：

  1. InitSString
  2. StrAssignSString
  3. StrCopySString
  4. StrEmptySString
  5. StrCompareSString
  6. StrLengthSString
  7. SubStringSString
  8. ConcatSString
  9. ClearStringSString
  10. PrintSString
  11. InitHString
  12. StrAssignHString
  13. DestroyHString

匹配：

  1. IndexBF
  2. GetNextArray
  3. GetNextValArray
  4. IndexKMP
  5. CountPatternMatchesNonOverlapping
  6. CountPatternMatchesOverlappingBF
  7. PrintIntArray1Based

5.4 第5章 树与二叉树

代码主入口：第5章普通代码版

二叉树基础：

  1. InitBiTreeQueue
  2. EnqueueBiTree
  3. DequeueBiTree
  4. CreateNode
  5. CreateBiTreeByPreorder
  6. DestroyBiTree
  7. PreorderTraversal
  8. InorderTraversal
  9. PostorderTraversal
  10. LevelOrderTraversal
  11. CountNodes
  12. CountLeaves
  13. CountDegreeOne
  14. CountDegreeTwo
  15. GetBiTreeHeight
  16. FindNodeLevel
  17. SwapChildren
  18. PrintTraversalResult

线索二叉树：

  1. CreateThreadNode
  2. CloneBiTreeToThreadTree
  3. DestroyThreadTree
  4. InorderThreading
  5. BuildInorderThreadedTree
  6. FirstInorderThreadNode
  7. NextInorderThreadNode
  8. InorderThreadTraversal

树 / 森林转换：

  1. CreateGTreeNode
  2. DestroyGTree
  3. PreRootTraversal
  4. PostRootTraversal
  5. PreorderForestTraversal
  6. ConvertTreeToBinaryTree
  7. ConvertForestToBinaryTree
  8. ConvertBinaryTreeToGTree
  9. BuildSampleGeneralTree
  10. BuildSampleForest

并查集与哈夫曼：

  1. InitUnionFind
  2. FindSet
  3. UnionSets
  4. PrintUnionFindState
  5. SelectTwoMinNodes
  6. BuildHuffmanTree
  7. ComputeHuffmanWPL
  8. PrintHuffmanTree

5.5 第6章 图

代码主入口：第6章普通代码版

存储与基本操作：

  1. InitAMGraph
  2. LocateVertexAM
  3. AddEdgeAM
  4. PrintAMGraph
  5. CreateArcNode
  6. InitALGraph
  7. LocateVertexAL
  8. AddArcNode
  9. AddEdgeAL
  10. PrintALGraph
  11. DestroyALGraph

遍历：

  1. DFSAM
  2. BFSAM
  3. DFSAL
  4. BFSAL
  5. CountConnectedComponentsAM

应用：

  1. TopologicalSortAL
  2. KruskalMSTWeightAM
  3. PrimMSTWeightAM
  4. FloydAM
  5. PrintFloydDistances
  6. PrintFloydPathAM
  7. DijkstraAM
  8. PrintDijkstraResult
  9. GetTopologicalOrderAL
  10. CriticalPathAL
  11. PrintCriticalPathResult
  12. BuildSampleGraphs
  13. BuildSampleDAG
  14. BuildSampleWeightedUndirectedGraph
  15. BuildSampleWeightedDirectedGraph
  16. BuildSampleAOEGraph

5.6 第7章 查找

代码主入口：第7章普通代码版

线性查找：

  1. SeqSearch
  2. BinarySearchIter
  3. BinarySearchRecursive
  4. BlockSearch

BST / AVL：

  1. CreateBSTNode
  2. BSTSearch
  3. BSTInsert
  4. BSTFindMin
  5. BSTDelete
  6. BSTInorder
  7. DestroyBST
  8. AVLHeight
  9. CreateAVLNode
  10. UpdateAVLHeight
  11. GetBalanceFactor
  12. RotateRight
  13. RotateLeft
  14. AVLInsert
  15. AVLSearch
  16. AVLPreorder
  17. DestroyAVL

红黑树：

  1. IsRedRB
  2. CreateRBNode
  3. RBRotateLeft
  4. RBRotateRight
  5. RBFlipColors
  6. RBInsert
  7. RBSearch
  8. RBMoveRedLeft
  9. RBMoveRedRight
  10. RBFixUp
  11. RBMin
  12. RBDeleteMin
  13. RBDelete
  14. RBInorder
  15. DestroyRB

B 树 / B+ 树：

  1. CreateBTreeNode
  2. BTreeSearch
  3. BTreeSplitChild
  4. BTreeInsertNonFull
  5. BTreeInsert
  6. BTreeFindKey
  7. BTreeGetPredecessor
  8. BTreeGetSuccessor
  9. BTreeMergeChildren
  10. BTreeBorrowFromPrev
  11. BTreeBorrowFromNext
  12. BTreeFillChild
  13. BTreeDeleteFromNode
  14. BTreeDelete
  15. BTreePrint
  16. DestroyBTree
  17. CreateBPlusNode
  18. BPlusFirstKey
  19. BPlusRefreshKeys
  20. BPlusInsertIntoLeaf
  21. BPlusInsertRecursive
  22. BPlusInsert
  23. BPlusBorrowFromPrev
  24. BPlusBorrowFromNext
  25. BPlusMergeChildren
  26. BPlusDeleteRecursive
  27. BPlusDelete
  28. BuildSampleBPlusTree
  29. BPlusFindLeaf
  30. BPlusSearch
  31. BPlusPrintRange
  32. BPlusPrintLeaves
  33. DestroyBPlusTree

Hash 表：

  1. HashFunc
  2. InitHashOpenTable
  3. HashOpenInsert
  4. HashOpenSearch
  5. PrintHashOpenTable
  6. CreateChainNode
  7. InitChainHashTable
  8. ChainHashInsert
  9. ChainHashSearch
  10. PrintChainHashTable
  11. DestroyChainHashTable

5.7 第8章 排序

代码主入口：第8章普通代码版

内部排序：

  1. InsertSort
  2. BubbleSort
  3. SelectionSort
  4. Partition
  5. QuickSort
  6. SiftDown
  7. HeapSort
  8. Merge
  9. MergeSortRecursive
  10. MergeSort
  11. CountingSort

非比较型排序：

  1. GetMaxValue
  2. CountingSortByDigit
  3. RadixSortLSD

外部排序与外排支撑：

  1. PrintRuns
  2. MergePass
  3. ExternalMergeSortSimulation
  4. LoserTreeAdjust
  5. BuildLoserTree
  6. LoserTreeDemo
  7. ReplacementSelectionRuns
  8. CopyArray

6. 原 PDF 与增强版的推荐对照方式

如果你还需要偶尔做原书对照，最推荐这样用：

  1. 先在这份索引里定位术语、公式或函数
  2. 再打开对应章节 自学版.md
  3. 如果涉及代码，再进入对应章节的代码专题页查看普通代码版或逐行注释版
  4. 只有在做最后的原书核对时，再回 DS.pdf

也就是说，这份索引的作用，就是尽量把“回原 PDF”从默认动作变成最后手段。

7. 当前结论

到这里，这套总索引系统已经把原来最缺的一层补上了：

  1. 术语能总查
  2. 公式能总查
  3. 函数能总查
  4. 原 PDF 页码能总对齐

这会明显提升整套材料对原书的替代能力。