单元1 绪论

一、基本概念与术语

1.1 数据

数据是客观事物的符号表示，是信息的载体，是所有能输入计算机并被计算机程序处理的符号的总称。它不仅包括整型、实型等数值类型，还包括字符、声音、图像、视频等非数值类型。

1.2 数据元素

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。例如，在学生信息管理系统中，一条学生记录（学号、姓名、性别、成绩）即是一个数据元素。

1.3 数据项

数据项是构成数据元素的不可分割的最小单位。例如，学生记录中的“学号”或“姓名”字段即为数据项。

1.4 数据对象

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。例如，整数数据对象是所有整数的集合，学生数据对象是所有学生记录的集合。

二、数据结构的定义

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。这一定义强调了两个方面：

1. 数据结构由数据元素构成。

2. 数据元素之间必然存在某种关系（即结构）。

在数据结构这门学科中，“结构”即指数据元素之间的相互关系。数据结构研究的内容可归纳为三个层面：

• 数据元素之间的逻辑关系，称为逻辑结构。

• 数据元素及其关系在计算机内存中的表示，称为存储结构（物理结构）。

• 对数据结构所施加的运算及操作实现。

三、逻辑结构

逻辑结构是对数据元素之间抽象关系的描述，它与计算机的具体存储硬件无关，是独立于计算机的数学模型。换言之，逻辑结构是从具体问题中抽象出来的数据模型。

3.1 四种基本逻辑结构

根据数据元素之间关系的不同特征，逻辑结构可分为以下四种基本类型：

四、存储结构（物理结构）

存储结构是指逻辑结构在计算机存储介质中的具体实现，包括数据元素本身的存储以及元素之间关系的表示。同一种逻辑结构可以对应多种存储结构。

4.1 顺序存储结构

顺序存储结构利用一组地址连续的存储单元依次存放数据元素。数据元素之间的逻辑邻接关系通过物理地址的相邻性来体现。其特点是：

• 支持随机访问，可由首地址和下标直接计算任意元素的存储位置。

• 存储密度高，无需额外指针开销。

• 插入和删除操作需移动大量元素。

4.2 链式存储结构

链式存储结构利用一组地址任意（不必连续）的存储单元存放数据元素。元素之间的逻辑关系通过附加的指针字段来维护。其特点是：

• 不支持随机访问，访问特定元素需从表头开始顺序查找。

• 存储密度较低，每个结点需额外存储一个或多个指针。

• 插入和删除操作仅需修改指针，无需移动元素。

五、算法

5.1 算法的定义

算法是对特定问题求解步骤的一种描述，是指令的有限序列。算法是程序设计的基础，也是数据结构研究的重要内容。

5.2 算法的五大特征

5.3 算法与程序的区别

程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有穷性（例如操作系统是不断运行的循环程序），因此算法是程序的子集。

六、时间复杂度

6.1 基本概念

时间复杂度是衡量算法执行时间随问题规模增长趋势的指标。它独立于具体的软硬件环境，仅依赖于算法本身的逻辑结构。

• 问题规模（n）：算法处理的数据量大小。例如，排序算法中待排序元素的个数，矩阵乘法中矩阵的阶数。

• 基本操作：算法中执行频率最高的操作，其执行次数直接反映了算法的时间开销。通常是最深层循环内的核心语句。

• 频度：基本操作在算法执行过程中被重复执行的次数。

• 数量级：忽略频度中的低次项和常数系数后所得的增长主项，使用大O记号表示。

6.2 大O记号的定义

若存在正常数 c 和 n_0 ，使得当 n \geq n_0 时， T(n) \leq c \cdot f(n) ，则称 T(n) = O(f(n)) 。大O记号表示了算法时间复杂度的上界。

6.3 常见时间复杂度量级

按增长率从低到高排列：

O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)

6.4 典型算法的时间复杂度分析

示例一：矩阵乘法 问题规模为 n（矩阵阶数），基本操作为乘法运算。

for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
        for (k = 1; k <= n; k++)
            C[i][j] = C[i][j] + A[i][k] * B[k][j];

最内层乘法语句的执行次数为 n \times n \times n = n^3 ，故时间复杂度为 O(n^3) 。

示例二：在n个元素中查找最大值 问题规模为 n，基本操作为元素间的比较运算。

max = a[0];
for (i = 1; i <= n - 1; i++)
    if (a[i] > max) max = a[i];

比较语句的执行次数为 n – 1 次，忽略常数项，时间复杂度为 O(n) 。

6.5 时间复杂度计算规则

1. 循环嵌套：总时间复杂度为各层循环次数之积的数量级。

2. 顺序结构：总时间复杂度取各组成部分时间复杂度的最大值。

3. 分支结构：取各分支中时间复杂度的最大值（考虑最坏情况）。

6.6 最坏、最好与平均时间复杂度

• 最坏时间复杂度：在所有可能的输入情况下，算法执行时间的最大值，是最常用的衡量指标。

• 最好时间复杂度：算法执行时间的最小值。

• 平均时间复杂度：在所有可能输入等概率出现时，算法执行时间的加权平均值。

七、易混淆概念辨析

1. 逻辑结构与物理结构的区分：逻辑结构是从应用角度对数据关系的抽象描述，与计算机无关；物理结构是逻辑结构在内存中的具体实现，与计算机体系结构和编程语言相关。同一逻辑结构可以对应多种物理结构（例如线性表既可用顺序存储实现，也可用链式存储实现）。

2. 算法时间复杂度的本质：时间复杂度衡量的是算法运行时间的增长趋势，而非具体执行时间。两个算法的时间复杂度同为 O(n) 时，在实际运行中可能因常数因子不同而存在时间差异，但它们的增长量级相同。

3. 算法与数据结构的独立性：算法的设计与逻辑结构相关，但具体实现的效率受存储结构影响。同一算法在不同存储结构上的时间复杂度可能不同（例如在顺序表和链表上实现查找操作，时间复杂度均为 O(n)，但在特定查找策略如折半查找中，存储结构的限制会直接决定算法是否可行）。