数据结构基本概念
数据结构的核心是计算机存储和组织数据的方式,目的是提升后续数据访问效率,存储的通常是具有特定关系的数据集合。
核心术语定义
术语 | 定义 | 示例 |
---|---|---|
数据(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)`
空间复杂度
- 定义:算法运行期间所需的内存空间(包括存储数据、临时变量、指令等的空间)。
- 原则:空间复杂度越小,算法对内存的占用越少,越优。
好算法的标准
- 执行时间短(时间复杂度低)
- 占用空间少(空间复杂度低)
- 可读性好、易维护、可移植