915 定义

约 1769 个字预计阅读时间 6 分钟

数据结构：
- 相互之间存在一种或多种特定关系的 数据元素的集合，是计算机存储和组织的方式，包含三部分：数据的逻辑结构，数据的物理结构，数据的操作
逻辑结构：
- 数据元素之间逻辑关系的描述
存储结构：
- 数据元素在计算机中的存储及其逻辑关系的表现
数据操作：
- 对数据要进行的运算
数据类型：
- 一个值的集合和定义在该值上的一组操作的总称。
抽象数据类型(ADT)：
- 用户定义的，表示应用问题的数学模型，以及 定义在这个模型上的一组操作的总称。包含三部分：数据对象，数据对象上关系的集合，数据对象上操作的集合。
算法：
- 算法是对特定问题 求解步骤的一种描述，它是指令的有限序列。
算法的五个特性：
- 有穷性，确定性，可行性，输入，输出
算法的评价标准：
- 正确性，可读性，健壮性，效率和低存储需求
渐进复杂度：
- 算法中 基本操作重复执行的次数 是问题规模 \(n\) 的某个函数 \(f(n)\) , 即 \(T(n) = O(f(n))\) ,它表示 随问题规模 \(n\) 的增大，算法执行时间的增长率和 \(f(n)\) 的增长率相同，称为 渐进时间复杂度，简称时间复杂度
大 \(\Theta\) 符号：
- 对于函数 \(f(n)\) 和 \(g(n)\) , \(f(n)=\Theta(g(n))\),当且仅当 \(\exists \,c_1,c_2,n_0 >0\),使得 \(\forall n \ge n_0,0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)\)
时空制衡原则：
- 时空制衡原则是计算机算法设计的原则，要求在时间复杂度和空间复杂度之间进行权衡，尽可能地优化两者的性能。
程序设计的一些基本原则：
- 分解、抽象和信息隐蔽。
递归：
- 一个函数直接或间接地调用自己本身，称为递归
递归过程转换成非递归的实质：
- 将原由系统管理的 递归工作栈 改为由程序员管理（例如 C++中的std::stack)
递归工作栈的作用
- 将递归调用时的 实在参数 和 返回地址 传递给下一层递归
- 保存 本层参数 和 局部变量，以便从下一层返回本层时继续恢复使用
树：
- 树是由若干节点组成的有限集合，有唯一的根节点和若干不相交的子集组成，每个子集也是一棵树，称为根的子树
二叉树：
- 二叉树是由若干节点组成的有限集合，有唯一的根节点和若干不想交的子集组成，每个子集也是二叉树，分别称为左子树和右子树。
完全二叉树：
- 深度为 \(h\) ，有 \(n\) 个结点的二叉树，当且仅当每个结点都与满二叉树的编号从 \(1\) 到 \(n\) 一一对应，则称该二叉树为完全二叉树
Huffman 树：
- 具有 \(n\) 个叶子结点的二叉树中，带权路径长度最小的一棵树称为 Huffman 树
树的带权路径长度：
- 树中所有叶子结点的带权路径长度之和
生成树的代价：
- 如果连通图是一个带权图，则其生成树中的边也带权，生成树中所有边的权值之和称为生成树得到代价。
最小生成树：
- 带权连通图中总代价最小的生成树，称为最小生成树
拓扑排序：
- 将有向无环图中的所有顶点排成一个线性序列，使得图中任意一对顶点 \(u\) 和 \(v\) ,若存在 \(<u,v>\) ,则 \(u\) 在线性序列中出现在 \(v\) 之前
二叉排序树

二叉排序树是空树或者满足如下性质
- 左子树上所有结点的值都小于根节点的值
- 右子树上所有结点的值都大于根节点的值
- 左右子树都是二叉搜索树
平衡二叉树

平衡二叉树是空树或者满足如下性质
- 左子树和右子树深度之差的绝对值不大于 \(1\)
- 左子树和右子树都是平衡二叉树
平衡因子：二叉树上结点的左子树的深度减去右子树的深度称为该结点的平衡因子
图：图 \(G\) 由两个集合 \(V\) 和 \(E\) 组成，记为 \(G＝(V，E)\)，其中 \(V\) 是顶点的有穷非空集合，\(E\) 是两个顶点之间的关系的集合
路径：是一个顶点序列。
堆：堆是一棵完全树，每个节点的值都大于等于/小于等于其父亲的值。
动态查找：二叉搜索树，AVL, B/B+ 树，哈希表
B 树(多路平衡查找树)：

一颗 \(m\) 阶 B 树为空树，或满足如下性质：
- 根节点的叶子结点数为 \([2,m]\)
- 其他终端节点的叶子结点数为 \([\lceil m/2 \rceil ,m]\)
- 结点的孩子个数等于该结点中关键字个数加 \(1\)
- 所有叶结点都在最后一层，并且不带任何信息（可以视为折半查找树的失败结点）
失败结点:
- \(\frac{m^h - 1}{m - 1} \ge n + 1 \ge 2(\lceil m/2 \rceil )^{h-1}\)
B 树的插入：
1. 像二叉搜索树那样插入
2. 关键字的个数都在 \([\lceil m/2 \rceil - 1 ,m - 1]\) 里面
3. 超过了 \(m-1\) ,要进行分裂，在 \(\lceil m/2 \rceil\) 的地方分裂（1 base）
B 树的删除：
- 在终端结点（最底层非叶结点）上：
  1. 直接删除，删除后仍满足关键字个数\(\ge \lceil {m/2} \rceil\)
  2. 兄弟够借，旋转一波
  3. 兄弟不够借，合并向下移
- 在非终端结点上：
  1. 和该结点的前驱结点/ 后继结点交换
  2. 交换后，该结点变成了终端结点
  3. 删除该结点 --> 删除终端节点
B 树和 B+ 树的差异
- 结点关键字和字数的个数
- B+ 树的非叶结点仅索引作用，不含关键字
- B+ 树支持顺序查找, B 树不支持
- B 树中结点的关键字不重复
散列表的删除
- 不能物理的删除，只能标记删除，物理删除会隔断该记录其他同义词的查找路径
排序过程中的特点

比较容易区分的
- 插入排序：前半部分是有序的，元素的位置并不是最终的位置
- 选择排序：前半部分是有序的，元素的位置是最终的位置
- 冒泡排序：前半部分是有序的，元素的位置是最终的位置
- 堆排序：
  1. 大根堆，后面几个是递增的，且是最终位置。
  2. 小根堆，后面几个是递减的，且是最终位置。
- 归并排序：几个归并段内是有序的，不是最终的位置
- 希尔排序：等差数列的增大
- 快速排序：有枢轴划分为左右两侧
分块查找：

Created: December 18, 2023
Last update: April 24, 2026

915 定义

Discussion