# 数据结构 第一章 绪论 · 速览 > Arietids Learn · 个人课程复习笔记 > 在线阅读：https://learn.arietids.net/courses/data-structures/chapter-01-quick/ ## 核心定义 - 程序 = 数据结构 + 算法。 - **数据**：外界信息进入计算机后的统称，分数值型（int, float）与非数值型（bool, char, string）；**数据元素**：数据处理的基本单位，通常作为整体处理的一个数据个体；不可再分的字段通常称为数据项。 - **数据结构**：一组具有特定关系的同类数据元素的集合；研究内容 = 逻辑结构 + 存储结构 + 基本操作。 - **算法**：解决一个具体问题的方法和步骤。 ## 逻辑结构（四种） - 集合关系——同属一个集合、相互无其他关系、次序任意；线性关系——你先我后的**一对一**；树形关系——**一对多**；图关系——**多对多**。 - 前驱/后继：线性结构除队首均有唯一前驱、除队尾均有唯一后继；树中除根均有唯一前驱、可有多个后继；图中前驱与后继都可有多个。 ## 基本操作（七种） - 创建、清除、插入（增）、删除（删）、更新（改）、查找（查）、遍历（每个元素仅被访问一次）。 ## 存储结构 - 内存中既存元素的**值**，也存元素间的**关系**；操作的设计取决于逻辑结构，操作的**实现**依赖存储结构；存储方式要有利于基本操作的实现。 - **顺序存储**（数组）：连续空间，用地址有序性隐式表关系；元素地址 a+i·k（k 为单元素所占空间）。优：按序号直接访问；劣：需预先声明大小、需连续空间、插入删除效率低。 - **链式存储**（链表）：空间不要求连续，关系经**指针域**显式存储，链尾指针为 NULL。优：长度可动态变化、插入删除高效、存储利用率高；劣：不能按序号访问需从头遍历、每个元素额外耗一个指针域。 - 随机查询极多、插入删除极少时选**数组**。 ## 算法五特性与五要求 - 五特性：确定性（无二义）、有穷性（有限步内完成）、可行性（有限次基本操作可完成）、有输入（零或若干个）、有输出（通常一个或若干个可观察输出/效果）。 - 五要求：正确性、可读性、健壮性（注意边界条件与特殊值）、时间效率（TLE）、空间效率（MLE）。 - 影响运行时间的因素：问题规模、算法优劣（两项为重点）、编译器代码质量、计算机系统性能。 ## 时间复杂度 - **时间频度** T(n)：基本语句的实际执行次数（循环按实际运行次数计；分支按执行语句多的分支计）。例 `s=0; for(i=0;i - **大 O 定义**：存在常数 C 与 $N_0$，当 $N>N_0$ 时 $T(N)\le C\cdot F(N)$，则记 $T(N)=O(F(N))$。 - 计算两步法：① 找与 n 有关的循环、数循环体执行次数得 T(n)；② 取最高次项并去掉系数。无 n 相关语句则为 O(1)。 - 双重无关联循环 $\sum\sum 1=n^2 \Rightarrow O(n^2)$；关联循环（j - **求和定理**：顺序两段 $T_1+T_2=O(\mathrm{MAX}(f(n),g(n)))$；**求积定理**：嵌套 $T_1\times T_2=O(f(n)\times g(n))$；关联循环可按内层最坏 O(n) 用求积得 $O(n^2)$。 - 常见量阶（效率高→低）：$O(1) - O(f(n)) 只给**量阶**不给精确值；分最好/最坏/平均三种情况，**一般取最坏情况**。 - 查找对比：有序序列二分查找最多 $\log_2 N+1$ 次，顺序查找最坏 N 次；N=10000 时后者超前者 1000 倍。 ## 空间复杂度 - 空间消耗三方面：程序本身、待处理数据、**额外辅助空间**；前两者不可避免，设计算法主要关注辅助空间。 - **空间复杂度** $S(n)=O(f(n))$：n 趋于无穷时辅助空间的量阶。逆置用辅助数组 b 为 O(n)；原地用临时变量 t 为 O(1)。 - 无临时变量交换两数：加减法、乘除法、三句异或法、Python 的 a,b=b,a；加减/乘除有溢出或除零限制，异或只适用于整数，C/C++ 不建议使用链式 `a^=b^=a^=b`。 - 内存足够大时优先时间效率；仅当时间复杂度一致时才比较空间复杂度。 - 空间换时间：哈希算法（输入经散列得键值；为降低哈希冲突需保留大量空位）；时间换空间：操作系统用硬盘充当内存（swap），换回数据耗时导致卡顿。 ## 本章研究框架 - 四个研究方面：逻辑结构及基本操作（完全脱离计算机分析，给出伪代码描述的抽象数据类型）→ 物理结构（顺序/链式）→ 基本操作实现（算法及时间/空间复杂度比较）→ 典型应用。