学校-数据结构知识点总结

数据结构知识点总结

本文围绕“数据结构基础-线性结构-树形结构-图形结构-查找-排序”的逻辑展开。

一、数据结构与算法基础

1. 数据结构核心概念

• 基本术语：
  • 数据：客观事物的符号表示（如图像、声音）。
  • 数据元素：数据的基本单位（如一条学生记录）。
  • 数据项：数据元素的不可分割最小单位（如学生记录中的“学号”“姓名”）。
  • 数据对象：具有相同性质的数据元素集合（如所有学生记录）。
  • 数据结构：相互存在特定关系的数据元素集合，形式定义为二元组 $Data Structure=(D, S)$（$D$ 为数据元素有限集，$S$ 为 $D$ 上关系有限集）。
• 数据结构三要素：
  1. 逻辑结构：数据元素间的逻辑关系（与存储无关）：
     • 线性结构：元素间“一对一”（如线性表、栈、队列、串、数组）。
     • 非线性结构：元素间“一对多”（树）、“多对多”（图）或无明确关系（集合）。
  2. 存储结构（物理结构）：数据在计算机中的表示，共4种：
     • 顺序存储：逻辑相邻元素物理也相邻（如数组），支持随机存取，插入/删除需移动元素。
     • 链式存储：用指针表示元素间关系（如链表），无需连续空间，插入/删除无需移动元素。
     • 索引存储：存储元素+索引表，适合快速查找。
     • 散列存储（哈希）：按关键字直接计算存储地址，查找效率高，需处理冲突。
  3. 数据的运算：对数据元素的操作（如插入、删除、查找）。

2. 算法核心概念

• 算法的5个基本特性：
  • 有穷性：执行有限步后结束，每步耗时有限。
  • 确定性：指令含义明确，相同输入必有相同输出。
  • 可行性：操作可通过基本运算有限次实现。
  • 输入：0个或多个输入。
  • 输出：1个或多个输出。
• “好算法”的4个目标：
  • 正确性：能正确求解问题。
  • 可读性：便于理解。
  • 健壮性：输入非法数据时能合理处理。
  • 效率与低存储：执行时间短，占用存储空间小。
• 算法效率度量（复杂度）：
  • 时间复杂度：分析语句频度之和 $T(n)$ 的数量级，核心是“找主导项”：
    • 加法规则：$T(n)=O(max(f(n),g(n)))$（取增长快的项）。
    • 乘法规则：$T(n)=O(f(n)×g(n))$。
    • 常见复杂度顺序：$O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)$。
  • 空间复杂度：算法执行所需最大存储空间（如数组占 $O(n)$，递归栈占 $O(log_2n)$）。

二、线性表之顺序表

1. 线性表基础

• 定义：具有相同数据类型的 $n(n≥0)$ 个数据元素的有限序列，记为 $L=(a_1,a_2,...,a_n)$：
  • 除首元素外，每个元素有且仅有一个直接前驱。
  • 除尾元素外，每个元素有且仅有一个直接后继。
• 基本操作：初始化、求表长、按位查找（$GetElem$）、按值查找（$LocateElem$）、插入（$ListInsert$）、删除（$ListDelete$）、判空、销毁。

2. 顺序表（线性表的顺序存储）

• 结构特点：
  • 用连续存储单元存储元素，逻辑相邻→物理相邻。
  • 静态分配：数组大小固定（如 #define MaxSize 50），易溢出；动态分配：用指针申请空间（malloc），可扩容。
  • 核心优势：随机存取（通过首地址+元素序号快速定位，时间 (O(1))）；存储密度高（仅存数据元素）。
• 核心操作：
  • 插入：在第 $i(1≤i≤L.length+1)$ 位插入，需将第 $i$ 位及后续元素右移，移动次数 $n-i+1$（$n$ 为表长）。
  • 删除：删除第 $i(1≤i≤L.length)$ 位元素，需将第 $i+1$ 位及后续元素左移，移动次数 $n-i$。
  • 合并有序顺序表：按“取较小元素”规则合并两个有序表，时间 (O(m+n))（(m,n) 为两表长度）。

三、线性表之链表

1. 单链表（线性表的链式存储）

• 结构特点：
  • 结点含“数据域”和“指针域”（指向后继结点），用头指针标识链表；通常加头结点（简化首元素操作，空表时头指针非空）。
  • 元素存储地址可连续可离散，无需预分配空间。
• 核心操作：
  • 查找：按序号查找（遍历，时间 (O(n))）、按值查找（遍历，时间 (O(n))）。
  • 插入：在第 (i) 位插入，需先找第 (i-1) 位前驱结点，指针操作 s->next=p->next; p->next=s（顺序不可颠倒）。
  • 删除：删除第 (i) 位元素，找第 (i-1) 位前驱结点，指针操作 p->next=p->next->next，释放待删结点。

2. 双链表与循环链表

• 双链表：
  • 结点含“前驱指针（prior）”和“后继指针（next）”，支持双向遍历。
  • 插入（在 (p) 后插 (s)）：s->next=p->next; if(p->next) p->next->prior=s; s->prior=p; p->next=s。
  • 删除（删 (p) 的后继 (q)）：p->next=q->next; if(q->next) q->next->prior=p; free(q)。
• 循环链表：
  • 单循环：尾结点指针指向头结点，判空条件 L->next==L。
  • 双循环：尾结点 next 指向头结点，头结点 prior 指向尾结点，空表时 L->next==L 且 L->prior==L。

四、栈与队列

1. 栈（操作受限的线性表）

• 核心概念：
  • 仅允许在“栈顶”插入（进栈）和删除（出栈），遵循“先进后出（LIFO）”。
  • 栈顶：操作端；栈底：固定端；空栈：无元素。
• 存储结构：
  • 顺序栈：用数组存储，栈顶指针 top 初始 -1，进栈 ++top 后存值，出栈取 top 值后 --top。
  • 链栈：用单链表存储，栈顶为表头，无栈满问题，进栈/出栈均为表头操作（时间 (O(1))）。
  • 共享栈：两个栈共享数组，栈底在两端，栈满条件 top1-top0==1（提高空间利用率）。

2. 队列（操作受限的线性表）

• 核心概念：
  • 仅允许在“队尾”插入（入队）、“队头”删除（出队），遵循“先进先出（FIFO）”。
  • 队头：删除端；队尾：插入端。
• 存储结构：
  • 顺序队列（循环队列）：
    • 用数组存储，队头指针 front（指向队头元素）、队尾指针 rear（指向队尾元素下一位）。
    • 判空：front==rear；判满：(rear+1)%MaxSize==front（预留一个空单元，避免与空队混淆）。
    • 元素个数：(rear+MaxSize-front)%MaxSize。
  • 链队列：用单链表存储，头指针指队头，尾指针指队尾，入队尾插、出队头删（时间 (O(1))）。

五、串与矩阵压缩存储

1. 串（特殊线性表）

• 核心概念：
  • 由零个或多个字符组成的有限序列，记为 $S='a_1a_2...a_n'$：
    • 空串：$n=0$；空格串：由空格组成（长度≠0）。
    • 子串：连续字符序列；主串：包含子串的串；子串位置：子串首字符在主串的位置。
    • 串相等：长度相同且对应字符相等。
• 基本操作：复制（StrCopy）、判空（StrEmpty）、比较（StrCompare）、求长（StrLength）、求子串（SubString）、连接（Concat）、模式匹配（BF算法：逐位比较子串与主串，时间 (O(mn))，(m,n) 为子串、主串长度）。

2. 矩阵压缩存储（节省空间）

• 对称矩阵：$a_{ij}=a_{ji}$，仅存下三角（含主对角线），一维数组下标 $k=\begin{cases}\frac{i(i-1)}{2}+j-1 & (i≥j) \\ \frac{j(j-1)}{2}+i-1 & (i<j)\end{cases}$。
• 下三角矩阵：上三角元素为常量，存下三角+常量，下标 $k=\frac{i(i-1)}{2}+j-1$（$i≥j$）。
• 稀疏矩阵：非零元素极少，用“三元组（行标,列标,值）”或“十字链表”存储，失去随机存取能力。

六、树与二叉树（1）

1. 树的基础

• 定义：$n(n≥0)$ 个结点的有限集，有且仅有一个根结点，其余结点分属若干子树（互不相交）。
• 核心术语：
  • 度：结点的孩子数；树的度：最大结点度；叶子结点：度为0的结点。
  • 层次：根为第1层；深度：根到结点的路径长度；高度：叶子到结点的路径长度。
• 树的性质：
  • 结点数=所有结点度之和+1。
  • 度为 $m$ 的树，第 $i$ 层最多 $m^{i-1}$ 个结点；高度 $h$ 最多 $\frac{m^h-1}{m-1}$ 个结点。

2. 二叉树

• 定义：每个结点最多两棵子树（左、右子树有序，不可颠倒），递归定义为空树或“根+左子树+右子树”。
• 特殊二叉树：
  • 满二叉树：高度 (h)，结点数 (2^h-1)（每层满结点）。
  • 完全二叉树：与同高度满二叉树的前 (n) 个结点一一对应（叶子仅在最后两层，左密右疏）。
  • 二叉排序树：左子树值<根值<右子树值（中序遍历递增）。
  • 平衡二叉树：任意结点左右子树深度差≤1。
• 二叉树性质：
  • 非空二叉树：叶子数 $n_0= n_2+1$（$n_2$ 为度2结点数）。
  • 第 (k) 层最多 (2^{k-1}) 个结点；高度 (h) 最多 (2^h-1) 个结点。
  • 完全二叉树编号：若结点编号 (i)，则双亲 (⌊i/2⌋)、左孩子 (2i)、右孩子 (2i+1)。
• 存储结构：
  • 顺序存储：适合完全二叉树，数组下标对应结点编号。
  • 链式存储（二叉链表）：结点含“数据域”“左孩子指针”“右孩子指针”，(n) 个结点有 (n+1) 个空链域。

3. 二叉树遍历

• 递归遍历：
  • 先序：根→左→右（visit(T); PreOrder(T->lchild); PreOrder(T->rchild)）。
  • 中序：左→根→右（InOrder(T->lchild); visit(T); InOrder(T->rchild)）。
  • 后序：左→右→根（PostOrder(T->lchild); PostOrder(T->rchild); visit(T)）。
• 层次遍历：用队列实现，根入队→出队访问→左/右孩子入队→重复至队空。

七、树与森林（2）及哈夫曼树

1. 树与森林的转换

• 树转二叉树：兄弟结点连线→保留第一个孩子，删其他孩子连线→顺时针旋转45°（根的右子树为空）。
• 森林转二叉树：每棵树转二叉树→根结点视为兄弟连线→顺时针旋转45°（第一棵树根为二叉树根，其余树为右子树）。
• 遍历对应关系：

  树	森林	二叉树
  先根遍历	先序遍历	先序遍历
  后根遍历	中序遍历	中序遍历

2. 二叉排序树（BST）

• 操作：
  • 插入：空树直接插，非空则比根值→左/右子树插入（新结点必为叶子）。
  • 删除：
    • 叶子结点：直接删。
    • 单孩子结点：子树替代该结点。
    • 双孩子结点：用“直接后继（右子树最小结点）”或“直接前驱（左子树最大结点）”替代，再删后继/前驱。

3. 哈夫曼树（最优二叉树）

• 核心概念：
  • 带权路径长度（WPL）：所有叶子结点“路径长度×权值”之和，哈夫曼树WPL最小。
• 构造方法：
  1. $n$ 个权值视为 $n$ 棵单结点树，构成森林。
  2. 选两棵根权最小的树，构造新结点（权=两树权和，左子树权≤右子树权）。
  3. 重复2，直至森林只剩一棵树。
• 哈夫曼编码：左分支0、右分支1，叶子结点编码唯一（前缀编码，无歧义）。

八、图（基础与遍历）

1. 图的基本概念

• 分类：
  • 按边方向：无向图（边无序，记为 $(v,w)$）、有向图（边有序，记为 $<v,w>$，v弧尾、w弧头）。
  • 按边数量：简单图（无重复边、无自环）、多重图（有重复边/自环）、完全图（无向：任意两顶点有边；有向：任意两顶点有双向弧）。
• 核心术语：
  • 连通（无向图）：两顶点有路径；连通图：任意两顶点连通；生成树：连通图的极小连通子图（边数=顶点数-1）。
  • 度：无向图顶点度=边数；有向图顶点入度（终点）、出度（起点），入度和=出度和=边数。
  • 网：边带权值的图。

2. 图的存储结构

• 邻接矩阵：
  • $n×n$ 矩阵，无向图对称：若 $(v_i,v_j)$ 存在，$A[i][j]=1$（网为权值），否则为0（网为∞）。
  • 特点：存储空间仅与顶点数有关（(O(n²))），适合稠密图；求度、判断边存在高效（(O(1))）。
• 邻接表：
  • 顶点表（存顶点信息+边表头指针）+边表（存邻接点下标+指针），适合稀疏图。
  • 特点：存储空间 (O(n+e))（(e) 为边数）；无向图边表需存两次，有向图求入度需遍历所有边表。

3. 图的遍历

• 深度优先搜索（DFS）：
  • 类似树先序，选起点→访问→递归访问未访问邻接点，用栈记录回溯路径，时间 (O(n+e))。
• 广度优先搜索（BFS）：
  • 类似树层次，选起点→访问→入队→出队→访问其未访问邻接点→入队，时间 (O(n+e))。
• 连通性：无向图若一次DFS/BFS访问所有顶点，则为连通图；否则为非连通图（需多次遍历）。

九、图的应用

1. 最小生成树（MST）

• 定义：带权连通无向图中，权值和最小的生成树（边数=顶点数-1）。
• 算法：
  • Prim算法：从某顶点出发，每次选“与当前树最近的顶点”及对应边，直至含所有顶点（适合稠密图）。
  • Kruskal算法：按边权从小到大选边，若不构环则加入，直至含所有顶点（用并查集判环，适合稀疏图）。

2. 最短路径（Dijkstra算法）

• 功能：求单源（某起点）到其他顶点的最短路径（边权非负）。
• 步骤：
  1. 初始化：起点距离0，其他顶点距离∞，标记起点已确定。
  2. 选未确定顶点中距离最小的 (u)，标记确定。
  3. 更新 (u) 邻接点的距离（若 (u) 到邻接点距离<当前距离，则更新）。
  4. 重复2-3，直至所有顶点确定。

3. 拓扑排序（AOV网）

• AOV网：顶点表示活动，边表示活动先后关系（无环有向图）。
• 排序步骤：
  1. 选无前驱（入度0）的顶点，输出。
  2. 删除该顶点及所有出边（邻接点入度-1）。
  3. 重复1-2，若输出顶点数<总顶点数，则有环（工程不可行）。
• 特点：拓扑序列不唯一。

4. 关键路径（AOE网）

• AOE网：顶点表示事件，边表示活动，边权表示活动耗时（无环有向图）。
• 核心参数：
  • 事件最早发生时间 (ve(k))：从源点到 (k) 的最长路径（活动最早开始时间 (e(i)=ve(起点))）。
  • 事件最迟发生时间 (vl(k))：从汇点到 (k) 的最短路径（活动最迟开始时间 (l(i)=vl(终点)-边权)）。
  • 关键活动：(l(i)-e(i)=0) 的活动，关键路径=关键活动构成的最长路径（决定工程最短工期）。

十、查找

1. 查找基础

• 核心概念：查找表（用于查找的数据集合）、关键字（标识数据元素，主关键字唯一）、平均查找长度（ASL，比较次数平均值）。

2. 顺序查找

• 适用：线性表（顺序/链式存储）。
• 方法：从一端遍历，对比关键字；带“哨兵”（表头/表尾存目标值）避免越界判断。
• ASL：成功 $(ASL=\frac{n+1}{2})$，不成功 $(ASL=n+1)$（(n) 为表长），时间复杂度 $(O(n))$。

3. 折半查找（二分查找）

• 适用：有序顺序表（链式存储不可用）。

• 方法：$(low=0, high=n-1)→(mid=(low+high)/2)$→对比 $(mid)$ 与目标→调整 $(low/high)$，直至找到或 $(low>high)$。

• ASL：成功 $(ASL≈log_2(n+1)-1)$，时间复杂度 $(O(log_2n))$。

• 核心概念：

  • 散列函数：关键字→存储地址（如除留余数法 $(H(key)=key\%p)$，$(p)$ 为接近表长的质数）。
  • 冲突：不同关键字映射同一地址（同义词）。

• 冲突处理：

  • 开放定址法：线性探测（冲突时顺次找空单元）、平方探测（冲突时找 $(H(key)±k²)）$。
  • 拉链法：同义词存同一链表，表头存在散列表中。

• 装填因子：$(\alpha=\frac{n}{m})$（$n$ 记录数，$m$ 表长），α越小冲突越少。

十一、排序

1. 排序基础

• 核心概念：
  • 稳定性：若 $(Key_i=Key_j)$ 且排序前 $i$ 在 $j$ 前，排序后仍如此，则稳定。
  • 内部排序：元素全在内存（重点）；外部排序：元素需内外存交换。

2. 常见排序算法（按类别）

类别	算法	时间复杂度（好/均/坏）	空间复杂度	稳定性	核心特点
插入排序	直接插入	$O(n)/O(n²)/O(n²)$	$O(1)$	稳定	适合基本有序数据，插入需移动元素
	希尔排序	$O(n)/O(n^{1.3})/O(n²)$	$O(1)$	不稳定	按增量分组插入，增量序列影响效率
交换排序	冒泡排序	$O(n)/O(n²)/O(n²)$	$O(1)$	稳定	每趟沉最小/大元素到最终位置，可优化（无交换则提前结束）
	快速排序	$O(nlog2n)/O(nlog2n)/O(n²)$	$O(log2n)$（递归栈）	不稳定	选枢轴分左右，平均效率最优，不适合有序数据
选择排序	简单选择	$O(n²)/O(n²)/O(n²)$	$O(1)$	不稳定	每趟选最小/大元素交换到有序区，移动次数少
	堆排序	$O(nlog2n)/O(nlog2n)/O(nlog2n)$	$O(1)$	不稳定	用大/小根堆，每趟选堆顶（最大/小）元素，适合大数据量
归并排序	二路归并	$O(nlog2n)/O(nlog2n)/O(nlog2n)$	$O(n)$	稳定	分治思想，合并两个有序表，适合外排序
基数排序	链式基数	$O(d(n+r))$（与初始无关）	$O(r)$	稳定	按位排序（不比较），$d$ 关键字位数，$r$ 基数（如10）

3. 算法选择建议

• 基本有序数据：直接插入、冒泡排序。
• 大数据量：堆排序、快速排序、归并排序。
• 需稳定排序：归并排序、基数排序、直接插入、冒泡排序。
• 内存受限：堆排序、希尔排序（空间 (O(1))）。