知识点库

数据结构是相互之间存在特定关系的数据元素的集合，包括逻辑结构、存储结构和数据运算三要素。

算法是对特定问题求解步骤的描述；五个特性：有穷性、确定性、可行性、输入、输出。

顺序表用连续存储空间实现线性表，支持随机访问O(1)，插入删除需移动元素O(n)。

由节点通过指针串联的线性结构，插入删除 $O(1)$，随机访问 $O(n)$。

顺序表有静态和动态两种实现方式，InitList初始化，核心是连续存储和长度管理。

单链表插入必须先让新节点指向后继，再修改前驱指针，顺序不可颠倒。

单链表删除需找到待删节点的前驱，修改前驱指针跳过待删节点后释放空间。

双链表每个节点有prior和next两个指针，插入删除需同时维护前后两个方向的指针。

循环链表尾节点指向头节点形成环，常用尾指针表示以便O(1)访问首尾。

静态链表用数组模拟链表，游标代替指针，适用于不支持指针的语言环境。

顺序表适合频繁访问，链表适合频繁插入删除，选择取决于操作特征和存储需求。

线性表是n个相同类型数据元素的有限序列，有唯一首元素和尾元素，元素间一对一关系。

线性表应用包括多项式表示、有序表合并、稀疏多项式运算等综合算法设计题。

栈是只允许在一端（栈顶）进行插入和删除的线性表，后进先出LIFO。

顺序栈用数组实现，top指针指示栈顶位置，入栈top++再赋值或先赋值再top++。

链栈用链表实现栈，栈顶为链表头部，入栈出栈均在表头操作，无栈满问题。

队列是只允许在队尾插入、队头删除的线性表，先进先出FIFO。

循环队列用取模运算解决假溢出，判满条件常用牺牲一个单元：(rear+1)%MaxSize==front。

链队列用链表实现队列，front指向队头，rear指向队尾，适合队列长度变化大的场景。

双端队列允许两端都可入队出队，输入受限/输出受限双端队列是常考变体。

栈应用：括号匹配、表达式求值（后缀表达式）、递归实现；队列应用：BFS、调度。

栈、队列和数组在算法中的综合应用，包括递归消除、滑动窗口、单调栈等。

数组是按下标随机访问的数据结构，行优先/列优先存储决定地址计算公式。

对称矩阵、三角矩阵、对角矩阵可压缩存储，用一维数组存储非重复元素。

稀疏矩阵非零元素远少于零元素，用三元组表或十字链表存储以节省空间。

n维数组地址计算是一维的推广，需要知道各维长度和存储方式（行/列优先）。

串是由零个或多个字符组成的有限序列，基本操作包括求子串、拼接、比较等。

朴素模式匹配逐位比较，失配时主串回退到起始位+1，最坏时间O(mn)。

KMP算法利用已匹配信息避免主串回退，通过next数组确定模式串回退位置，时间O(m+n)。

nextval是next数组的优化，当T[j]==T[next[j]]时进一步回退，减少无效比较。

前序=根左右，中序=左根右，后序=左右根；已知任意两种（必含中序）可还原。

哈夫曼树是带权路径长度WPL最小的二叉树，用于构造最优前缀编码。

二叉树顺序存储用数组按层序编号，适合完全二叉树，一般二叉树会浪费空间。

二叉链表每个节点含lchild、data、rchild三个域，n个节点有n+1个空指针。

二叉树每个节点最多两个子树，具有n0=n2+1等重要性质。

先序(根左右)、中序(左根右)、后序(左右根)遍历，递归和非递归实现，可由两种序列重建树。

层次遍历用队列实现，按层从上到下、从左到右访问所有节点。

线索二叉树利用空指针域存储前驱/后继信息，ltag/rtag区分孩子和线索。

树的先根遍历对应二叉树先序，树的后根遍历对应二叉树中序。

并查集支持合并和查找操作，路径压缩+按秩合并后近似O(1)。

树是n个节点的有限集合，有且仅有一个根节点，其余节点构成若干互不相交的子树。

树的存储有双亲表示法、孩子表示法和孩子兄弟表示法三种。

树转二叉树：左孩子右兄弟；森林转二叉树：各树的根通过右指针相连。

堆是完全二叉树，大顶堆每个节点≥其孩子，建堆O(n)，堆排序O(n log n)。

DFS用栈/递归实现深度优先，BFS用队列实现广度优先，邻接表时间O(V+E)。

图由顶点集V和边集E组成，分有向图和无向图，核心概念包括度、路径、连通性。

邻接矩阵用二维数组存储，空间O(V²)，适合稠密图，无向图矩阵对称。

邻接表用链表存储每个顶点的邻接点，空间O(V+E)，适合稀疏图。

DFS从一个顶点出发尽可能深入，用visited数组避免重复访问，生成DFS树。

BFS从起始顶点逐层扩展，用队列实现，可求无权图最短路径。

最小生成树：Prim适合稠密图O(V²)，Kruskal适合稀疏图O(E log E)。

Dijkstra求单源最短路径(非负权)O(V²)，Floyd求所有顶点对最短路径O(V³)。

拓扑排序对DAG的顶点排序使所有有向边从前指向后，可用于检测有向图是否有环。

关键路径是AOE网中从源点到汇点的最长路径，决定工程最短完成时间。

十字链表用于有向图，邻接多重表用于无向图，都是边为主体的存储结构。

顺序查找逐个比较，ASL成功=(n+1)/2，可设置哨兵减少比较次数。

折半查找要求有序顺序表，每次比较排除一半，ASL≈log₂(n+1)-1，判定树是平衡BST。

分块查找将表分为若干块，块间有序块内无序，索引顺序查找ASL介于顺序和折半之间。

二叉排序树左<根<右，查找效率取决于树形，最好O(log n)最坏O(n)。

AVL树任意节点左右子树高度差≤1，通过LL/RR/LR/RL四种旋转保持平衡，查找O(log n)。

B树是多路平衡查找树，所有叶子在同一层，适合磁盘存储，减少I/O次数。

B+树所有关键字都在叶子节点，叶子用链表相连，支持高效范围查询。

通过散列函数将关键字映射到存储位置，平均 $O(1)$；需处理冲突和装填因子。

散列查找性能取决于装填因子α、散列函数和冲突处理方法，α越大冲突越多。

查找的基本概念包括查找表、关键字、ASL（平均查找长度）等核心术语。

红黑树是近似平衡的BST，满足5条性质，插入删除最多旋转3次，比AVL树调整代价低。

字符串模式匹配是在主串中查找模式串的位置，朴素法O(mn)，KMP法O(m+n)。

各查找算法适用场景不同，需根据数据特征（有序性、动态性、存储方式）选择。

直接插入排序将元素逐个插入已排序序列的正确位置，O(n²)，稳定，对近乎有序数据高效。

希尔排序按递减增量分组进行插入排序，突破O(n²)，不稳定，时间约O(n^1.3)。

冒泡排序相邻元素两两比较交换，每趟将最大元素"冒泡"到末尾，O(n²)，稳定。

分治：选枢轴分区，左小右大。平均 $O(n\log n)$，最坏 $O(n^2)$，空间 $O(\log n)$。

简单选择排序每趟选最小元素放到前面，比较次数固定n(n-1)/2，不稳定。

堆排序利用堆的性质选择最值，建堆O(n)，排序O(n log n)，不稳定，原地排序。

归并排序将序列递归二分再合并，O(n log n)，稳定，需O(n)辅助空间。

基数排序按位分配收集，不基于比较，时间O(d(n+r))，稳定，适合关键字位数少的情况。

外部排序用于数据量超过内存的情况，核心是多路归并，用败者树和置换选择优化。

排序的基本概念包括稳定性、内部/外部排序、基于比较排序的下界Ω(n log n)。

折半插入排序用折半查找确定插入位置，比较次数O(n log n)但移动次数仍O(n²)，稳定。

各排序算法在时间、空间、稳定性、适用场景上各有优劣，需综合选择。