ZERO

基本概念排序算法的稳定性 指经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变。 稳定性是对算法性质的描述，并不能衡量一个算法的优劣。 若待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关重要。 对同一线性表使用不同的排序方法进行排序，得到的排序结果可能不同（除非每个关键字唯一）。 排序算法的分类 在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类： 内部排序 指排序期间元素全部存放在内存中的排序。 外部排序 指排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。 内部排序的比较与移动 一般情况下，内部排序算法在执行过程中基本要进行两种操作：比较、移动。通过比较两个关键字的大小，确定对应元素的前后关系，然后通过移动元素以达到有序。 移动的方式分为两种：插入、交换。插入排序属于插入，交换排序、选择排序属于交换。交换往往使得算法不稳定（除冒泡），插入则不会（除希尔）。 插入会使得插入点及其后序全部元素后移一位；而交换则是每交换一次需要元素移动 3 次，因为需要借助中间变量。不过堆排序 ...

基本概念查找 在数据集合中寻找满足某种条件的过程。 查找结果：成功、失败。 查找表 用于查找的数据集合。由同一类型的数据元素（或记录）组成。 对查找表的常见操作 查询某个特定元素是否在查找表中。 检索满足条件的某个特定的数据元素的各种属性。 插入。 删除。 静态查找表 只涉及上述 1 和 2 操作。 适合静态查找表的查找方法：顺序查找、折半查找、散列查找等。 动态查找表 需要动态地插入或删除的查找表。 适合动态查找表的查找方法：二叉排序树的查找、散列查找等。 关键字 数据元素中唯一标识该元素的某个数据项的值。 使用基于关键字的查找，查找结果应该是唯一的。 平均比较次数/平均查找长度 ASL ASL = $\sum^n_{i=1}P_i C_i$ $n$ 为查找表记录个数/长度；$P_i$ 为查找第 $i$ 个记录的概率，一般取 $\frac{1}{n}$，即认为每个数据元素的查找概率相等；$C_i$ 为找到第 $i$ 个记录需要比较的次数。 线性结构的查找顺序查找又称线性查找，对顺序表和链表都适用。 一般线性表 $ASL_{成功}=\frac{n+1}{2}$，$ASL_{失败}= ...

基本概念图的定义 图 G 由顶点的有限非空​集 V 和边集 E 组成 → G = (V, E)。 线性表可以是空表，树可以是空树，但图不可以是空图（边集可空，顶点集一定非空⚠）。 |V| 表示 G 中顶点 vertex 的个数，|E| 表示 G 中边 edge 的条数。 有向图 每条边都有方向。 无向图 每条边都没有方向。 边/无向边 无向图中的边，是顶点的无序对，记为 ($v_i$, $v_j$)，等价于有向图中 <$v_i$, $v_j$> 和 <$v_j$, $v_i$> 两条边。 可以说 $v_i$ 和 $v_j$ 互为邻接点。 边 ($v_i$, $v_j$) 依附于 $v_i$ 和 $v_j$，或称边 ($v_i$, $v_j$) 和 $v_i$、$v_j$ 相关联。 弧/有向边 有向图中的边，是顶点的有序对，记为 <$v_i$, $v_j$>，$v_j$ 为弧头，$v_i$ 为弧尾。 <$v_i$, $v_j$> 称从 $v_i$ 到 $v_j$ 的弧，也称 $v_i$ 邻接到 $v_j$。 度 度 TD($v ...

树基本概念树的定义 树是 $n$（$n \ge 0$）个结点的有限集。当 $n=0$ 时，称为空树。 任意非空树由唯一根结点与若干棵互不相交的子树组成（每一棵子树又是一棵树，递归定义）。 树作为一种逻辑结构，同时也是一种分层结构。 树的特点 根结点无前驱，其他所有结点有且只有一个前驱。 树中所有结点可以有零个或多个后继。 基本术语空树、结点的度（结点的孩子个数）、树的度（树中结点的最大度数）、叶子/终端结点（度为 0）、分支/非终端结点（度大于 0）、内部结点、孩子、双亲、兄弟、堂兄弟（双亲在同一层）、祖先、子孙、层次（根结点为第 1 层）、树的高度/深度（树中结点的最大层数）、结点深度（自顶向下逐层累加）、结点高度（自底向上逐层累加）、有序树（树中结点的各子树左右有序，不能互换）、无序树、路径（结点序列）、路径长度（路径上所经过的边的个数）、丰满树/理想平衡树（除最底层外其他层都是满的）、森林（若干棵互不相交的树的集合）。 ⚠分支有向（从双亲指向孩子），路径只能自顶向下，故同一双亲的两个孩子之间不存在路径。 “路径长度” 结点的路径长度：根到该结点经过的边数。 ...

串的定义和实现串的定义 字符串简称串，是由零个或多个字符组成的有限序列。 空串：含 0 个元素的串（长度为 0），用 $\varnothing$ 表示。 空格串：由 1 个或多个空格组成的串。 串与线性表 在逻辑结构上：串和线性表即为相似，区别仅在于串的数据对象限定为字符集。 在基本操作上：串和线性表有很大差别。线性表的基本操作主要以单个元素为操作对象，而串的基本操作通常以子串为操作对象。 串的存储结构 顺序存储结构 —— 定长顺序存储表示、堆分配存储表示 串长可以用一个额外变量保存；也可以在串值末尾加一个不计入串长的结束标记字符 ‘\0’，此时的串长为隐含值。 链式存储结构 —— 块链存储表示 每个结点可以存放 $n$ 个字符（$n \ge 1$）。每个结点称为块，整个链表称为块链结构。 串的基本操作 最小操作子集：赋值、比较、求串长、求子串、串联接。 其他操作：复制、判空、子串定位（模式匹配）、清空、销毁。 最小操作子集中的操作不可能由其他串操作来实现；反之，其他串操作（除串清空和串销毁外）均可在该最小操作子集上实现。 串的模式匹配子串的定位操作通常称为串的模式匹配 ...

栈概念栈的数学性质 出栈排列数目（$n$ 个不同元素以某种顺序依次进栈，并可在任意时刻出栈）满足函数 $Catalan()$：$N=\frac{1}{n+1}C^n_{2n}$。 栈的基本操作 初始化、判空、进栈 push、出栈 pop、读栈顶、销毁。 顺序存储结构顺序栈 判空、判满条件以及进栈、出栈的操作顺序（先改指针还是先存取元素），会因实际给的条件不同而变化（主要取决于初始栈顶指针的位置），因此需要具体问题具体分析。 共享栈 利用栈底位置相对不变的特性，让两个顺序栈共享一个一维数组空间： 采用共享栈的好处：更有效地利用存储空间；降低发生上溢的可能。 链式存储结构链栈 通常采用单链表实现，并规定所有操作都是在单链表的表头进行。 不存在栈满上溢的情况。 应用栈的常见/常考应用 括号匹配、表达式求值、调用函数（递归调用、子程序调用）、进制转换、迷宫求解。 递归递归定义 若在一个函数、过程或数据结构的定义中又应用了它自身，则这个函数、过程或数据结构称为是递归定义的，简称递归。 递归模型 递归模型不能是循环定义的，其必须满足下面的两个条件： 边界条件（递归出口） 递归表达式（ ...

定义和基本操作线性表 具有相同数据类型的 $n$ 个数据元素的有限序列（$n \geq 0$）。 空表：表长 $n$ 为 0 线性表的逻辑特性 ⚠表中元素的个数有限。 ⚠表中元素具有逻辑上的顺序性，表中元素有其先后顺序。 表中元素都是数据元素，每个元素都是单个元素。 表头元素唯一，表尾元素唯一。 表头无前驱，表尾无后继。 除表头表尾，每个元素有且仅有一个直接前驱和一个直接后继。 ⚠表中元素的数据类型都相同（意味着每个元素占有相同大小的存储空间）。 线性表的基本操作 初始化、求表长、判空、插入、删除、按值查找、按位查找、打印、销毁。 存储结构 顺序表示顺序表 线性表的顺序存储又称顺序表。 顺序表的特点 表中元素的逻辑顺序与其物理顺序相同； 每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数； 通过首地址和元素序号可在时间 O(1) 内找到指定的元素，即可随机存取。 通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。 线性表中元素的位序从 1 开始，数组中元素下标从 0 开始。 存储空间连续，分配只能 ...

数据结构的基本概念数据 信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。 例如：整数、实数、字符串。 数据元素 数据的基本单位，通常作为一个整体进行考虑和处理。 例如：一名学生的记录。 数据项/数据域 构成数据元素的不可分割的最小单位。 例如：一名学生的记录由学号、姓名、性别等数据项组成。 数据对象 性质相同的数据元素的集合，是数据的一个子集。 例如：整数数据对象是集合 N = {0, ±1, ±2, ……}。 数据类型 一个值的集合和定义在此集合上的一组操作的总称。 分为： 1）原子类型：其值不可再分的数据类型。 2）结构类型：其值可以再分解为若干成分（分量）的数据类型。 3）抽象数据类型 ADT (Abstract Data Type)：一个数据模型及定义在该数学模型上的一组操作。它通常是对数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据操作的集合。 数据结构 相互之间存在一种或多种特定关系的数据元素的集合。 二元组 (D, S) 表示：D 是数据元素的有限集，S 是 D 上关系的有限集。 三要素：逻辑结构、存储结构 ...