数据结构基本概念
数据结构的核心是计算机存储和组织数据的方式，目的是提升后续数据访问效率，存储的通常是具有特定关系的数据集合。
核心术语定义
| 术语 | 定义 | 示例 |
|---|---|---|
| 数据（Data） | 可输入计算机并被处理的符号总称 | 学生信息、数字、文本等 |
| 数据元素 | 数据的基本单位，计算机中作为整体处理 | 单个学生的完整信息 |
| 数据项 | 数据的最小单位，不可分割，组成数据元素 | 学生的学号、姓名、年龄 |
| 数据对象 | 多个相同类型数据元素的集合 | 一个班级所有学生的信息、世界上所有国家 |
| 数据结构 | 描述数据元素之间的逻辑结构（关系）和物理结构（存储方式） | 数组（逻辑线性 + 物理顺序）、链表（逻辑线性 + 物理离散） |
数据结构的两大构成
数据元素的逻辑关系与物理关系无必然联系，可能同时存在、仅存一种或均不存在。
-
逻辑结构：数据元素之间的逻辑关系，分 4 类：
-
集合结构：元素间无任何关系（仅属于同一集合）
-
线性结构：元素间为一对一关系（如排队队伍、学号序列）
-
树状结构：元素间为一对多关系（如公司组织架构、家谱）
-
图状结构：元素间为多对多关系（如社交网络、交通路线图）
-
-
物理结构（存储结构）：数据在计算机中的实际存储方式，分 2 类：
-
顺序结构（连续存储）：数据存于连续内存单元，可通过首地址计算任意元素地址（如数组）。
-
链式结构（离散存储）：数据存于不连续内存单元，需通过指针 / 引用关联元素，无法直接计算后续元素地址（如链表）。
-
算法基础
算法是数据结构的 “操作逻辑”，二者结合构成程序（程序 = 数据结构 + 算法）。
算法定义
- 广义：研究数据逻辑关系，选择存储方案并处理数据的过程。
- 直白解释：解决问题的具体步骤（如排序算法 = 将无序数列变为有序的步骤）。
算法的 5 大特征
| 特征 | 要求 |
|---|---|
| 有穷性 | 程序需在有限次数内完成，且每步执行时间有限 |
| 确定性 | 每一条语句无歧义，相同输入必对应相同输出 |
| 可行性 | 复杂语句可分解为基本指令，且每条基本指令能在有限时间内完成 |
| 输入项 | 可包含 0 个或多个初始参数（0 个输入即无初始条件） |
| 输出项 | 必须有 1 个或多个输出（无输出的算法无意义） |
算法的衡量标准：复杂度
选择算法的核心是平衡时间复杂度和空间复杂度（二者通常相互制约，“鱼和熊掌不可兼得”）。
时间复杂度
-
定义：算法语句的执行次数（语句频度），而非实际运行时间（运行时间依赖 CPU 性能）。
-
表示方法：用数学符号大 O () 表示，描述算法执行次数随数据规模（通常用
n表示）增长的 “趋势”。 -
计算技巧：
- 只保留最高次项（最高次项对执行次数影响最大）；
- 舍弃最高次项的系数；
- 若结果为常数（与
n无关），则时间复杂度为O(1)。
-
示例：
// 示例1：n为数据规模 for (int i=0; i < n; ++i) { // 循环执行n次printf("hello\n"); // 核心语句执行n次 } // 总执行次数：3n+2（多项式）→ 保留最高次项n，舍系数 → 时间复杂度O(n)`// 示例2：无数据规模n（固定次数） for (int i=0; i < 10; ++i) { // 固定执行10次printf("hello\n"); } // 总执行次数为常数 → 时间复杂度O(1)`
空间复杂度
- 定义：算法运行期间所需的内存空间（包括存储数据、临时变量、指令等的空间）。
- 原则：空间复杂度越小，算法对内存的占用越少，越优。
好算法的标准
- 执行时间短（时间复杂度低）
- 占用空间少（空间复杂度低）
- 可读性好、易维护、可移植