数据结构

顺序存储（顺序表）：
特点：物理位置邻接表示逻辑关系，可随机存取
优点：查找快，存储密度高
缺点：插入删除需移动大量元素

链式存储（链表）：
特点：用任意存储单元存放，逻辑次序与物理次序不一定相同
类型：单链表、循环链表、双向链表
优点：插入删除方便
缺点：查找需遍历，存储密度低

栈（Stack）
定义：限定只在表尾（栈顶）进行插入和删除的线性表
特点：后进先出（LIFO）
基本操作：入栈（Push）、出栈（Pop）、读栈顶
应用场景：表达式求值、括号匹配、函数调用、递归实现

队列（Queue）
定义：只允许在表一端插入（队尾）、另一端删除（队头）的线性表
特点：先进先出（FIFO）
循环队列：解决假溢出问题，队空队满判断条件
应用场景：任务调度、缓冲区、广度优先搜索

串（String）
定义：由零个或多个字符组成的有限序列
子串：主串中任意连续字符组成的子序列，位置从第一个字符首次出现位置算起
模式匹配：KMP算法（重点：next数组计算）

数组和广义表
数组：
多维数组的存储：行优先、列优先
二维数组地址计算（按行存储）
特殊矩阵压缩存储：
对称矩阵：存储下三角
三对角矩阵：k = 2i + j - 3
稀疏矩阵：三元组表、十字链表

广义表：
线性表的推广，元素可以是单元素或子表
长度：最外层元素个数；深度：括号嵌套的最大层数
表头、表尾操作

二叉树
定义：每个结点最多有两棵子树的树结构

重要性质：
第i层最多有 2^(i-1) 个结点（i≥1）
深度为k的二叉树最多有 2^k - 1 个结点（k≥1）
终端结点数n0与度为2的结点数n2关系：n0 = n2 + 1
具有n个结点的完全二叉树深度为 ⌊log₂n⌋ + 1
满二叉树：每层都满
完全二叉树：除最后一层外都满，且最后一层结点靠左排列

二叉树的遍历
先序遍历：根 → 左 → 右
中序遍历：左 → 根 → 右
后序遍历：左 → 右 → 根
层次遍历：从上到下，从左到右

树与二叉树的转换
转换规则：左孩子不变，兄弟结点变为左孩子的右孩子
遍历对应关系：树的前序 = 二叉树的先序；树的后序 = 二叉树的中序

图
基本概念：顶点、边（弧）、有向图、无向图、完全图、度
重要结论：
有向图中，所有顶点出度数之和 = 入度数之和
图中边数 = 所有顶点度数之和的一半
存储结构：邻接矩阵、邻接表
遍历：深度优先搜索（DFS）、广度优先搜索（BFS）
应用：最小生成树（Prim、Kruskal）、最短路径（Dijkstra、Floyd）、拓扑排序

动态查找表
二叉排序树（查找二叉树）：
定义：左子树所有结点值 < 根结点值 < 右子树所有结点值
中序遍历结果有序
查找效率与树的高度相关
平衡二叉树（AVL树）：
定义：任一结点左右子树深度差不超过1
平衡因子：右子树深度 - 左子树深度（取值-1,0,1）
B树：多路平衡查找树，用于文件系统和数据库索引

散列查找
散列表：根据关键码值直接访问的数据结构
散列函数：构造方法（直接定址法、除留余数法、数字分析法等）
冲突处理：
开放定址法（线性探测、二次探测、伪随机探测）
链地址法
再散列法
装填因子：α = 表中记录数 / 散列表长度

排序算法