基本概念与线性表

本节导读

数据结构这一门从这里开始。本节先讲常见资料称 2025 年版新增的「基本概念」一章：数据结构的基本概念、算法的基本概念与复杂度分析；再讲线性表的顺序存储和链式存储；最后讲算法设计题的答题框架。

单项选择题里，复杂度计算、顺序表与链表的操作特点都可以单独出题；综合应用题里的算法设计题，数组和链表是练答题框架最合适的材料。学完你应该能算出一段循环或递归的复杂度，能写出链表插入、删除、逆置的代码，并按三段式写出一道算法设计题。

数据结构的基本概念

数据元素是数据的基本单位，数据项是构成数据元素的不可分割的最小单位；性质相同的数据元素的集合叫数据对象。抽象数据类型（ADT）用「数据对象 + 数据关系 + 基本操作」描述一个数学模型，与具体实现无关。

数据结构有三要素：逻辑结构、存储结构（物理结构）和数据的运算。逻辑结构分四类：

逻辑结构	元素之间的关系	典型例子
集合	同属一个集合，别无其他关系	一组互不相关的编号
线性结构	一对一	线性表、栈、队列、串
树形结构	一对多	树、二叉树、并查集
图状结构	多对多	有向图、无向图

存储结构也有四种：顺序存储（逻辑上相邻的元素物理位置也相邻）、链式存储（借助指针表示关系）、索引存储（另建索引表）、散列存储（由关键字直接算出地址）。同一种逻辑结构可以采用不同的存储结构，比如第 3 节的栈就有顺序栈和链栈两种；运算的定义针对逻辑结构，运算的实现针对存储结构。

算法与复杂度

算法的五个特性

有穷性（有限步内结束）、确定性（每一步含义确切，相同输入得到相同输出）、可行性（能用已实现的基本运算完成）、输入（零个或多个）、输出（一个或多个）。设计算法时还追求正确性、可读性、健壮性和高效率低存储量，这几条是「好算法」的目标，不属于五个特性。

时间复杂度

时间复杂度看基本语句（一般是最深层循环里的语句）执行次数的数量级，记作 $T(n) = O(f(n))$T(n)=O(f(n))。加法规则取较大的一项，乘法规则相乘。常见的阶从小到大是：

$$\begin{aligned} & O(1) \lt O(\log_2 n) \lt O(n) \\ & \lt O(n\log_2 n) \lt O(n^2) \lt O(n^3) \\ & \lt O(2^n) \lt O(n!) \lt O(n^n) \end{aligned}$$​O(1)<O(log2​n)<O(n)<O(nlog2​n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)​

分析循环的通用办法：设循环执行了 t 次，写出循环变量与 t 的关系，再由循环条件解出 t。例如 i = 1; while (i <= n) i = i * 2;，执行 t 次后 $i = 2^t$i=2t，由 $2^t \le n$2t≤n 得 $t \le \log_2 n$t≤log2​n，时间复杂度为 $O(\log_2 n)$O(log2​n)。嵌套循环要把每次外层循环里内层的执行次数加起来，不能见到两层就写平方。复杂度还分最好、最坏和平均情况，不特别说明时一般指最坏情况。

空间复杂度

空间复杂度只算除输入数据以外的辅助空间。辅助空间是常数时叫原地工作，记作 $O(1)$O(1)。递归算法要把系统栈算进去：每层递归占常数空间时，空间复杂度与递归深度同阶。例如折半查找写成递归时，每次规模减半，递归深度约 $\log_2 n$log2​n，空间复杂度是 $O(\log_2 n)$O(log2​n)。

线性表的顺序存储

线性表是 n 个相同类型数据元素的有限序列，除第一个元素外每个元素有唯一的直接前驱，除最后一个外有唯一的直接后继。用一组地址连续的存储单元依次存放线性表的元素，就是顺序表。每个元素占 L 个存储单元时：

$$\mathrm{LOC}(a_i) = \mathrm{LOC}(a_1) + (i-1) \times L$$LOC(ai​)=LOC(a1​)+(i−1)×L

所以顺序表能随机存取，按序号读写是 $O(1)$O(1)。插入和删除要移动元素（位序从 1 起，表长为 n）：

操作	移动元素的个数	等概率下的平均	时间复杂度
在第 i 个位置插入（$1 \le i \le n+1$1≤i≤n+1）	$n - i + 1$n−i+1 个后移	$\dfrac{n}{2}$2n​	$O(n)$O(n)
删除第 i 个元素（$1 \le i \le n$1≤i≤n）	$n - i$n−i 个前移	$\dfrac{n-1}{2}$2n−1​	$O(n)$O(n)
按值查找	比较次数平均 $\dfrac{n+1}{2}$2n+1​	—	$O(n)$O(n)

例如在长度为 10 的顺序表第 3 个位置插入，要把第 3 至第 10 个元素后移，共 10 − 3 + 1 = 8 个。

线性表的链式存储

单链表的结点由数据域 data 和指针域 next 组成。通常在第一个结点前加一个头结点：空表与非空表、第一个位置与其他位置的操作就统一了。下面是结点定义和两个基本操作（p 指向某个结点，s 指向新结点）：

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode;
/* 在 p 之后插入 s：先连后断 */
s->next = p->next;
p->next = s;
/* 删除 p 的后继结点 */
q = p->next;
p->next = q->next;
free(q);

用头插法建表，读入的顺序与链表中的顺序相反；用尾插法（多一个尾指针）顺序相同。双链表的结点多一个前驱指针 prior，找前驱是 $O(1)$O(1)；循环链表让最后一个结点指回头结点，从任一结点出发都能走遍全表；静态链表用数组存结点、用数组下标（游标）当指针，适合不支持指针的语言。

比较项	顺序表	链表
存取方式	随机存取	顺序存取，按序号访问要从头走
插入删除	平均移动约一半元素	不移动元素，改指针；但先要找到位置
存储密度	等于 1	小于 1（每个结点多存指针）
空间分配	预先分配，扩充要整体搬移	按需申请结点

算法设计题怎么答

算法设计题一般给出数组、链表或树，要求设计在时间上（或时间、空间都）尽可能高效的算法。答题分三段：

1. 基本设计思想：用几句话说清用什么方法、关键步骤是什么。
2. 用 C 语言描述算法：写出函数头（参数类型要清楚），关键语句加注释。
3. 说明时间复杂度和空间复杂度。

想不出最优解时，先写一个正确的暴力解法保底，再看能不能优化。常用的优化手段：

手段	适用场合
双指针	一前一后或一快一慢扫描，原地删除、合并、找中点
就地逆置	数组或链表整体或分段反转
计数或标记数组	元素取值范围有限时，用空间换时间
先排序再处理	排序后相同或相近的元素挨在一起

易错提醒

• ❌ 两层嵌套循环的时间复杂度一定是 $O(n^2)$O(n2)。✅ 要把每次外层循环里内层的执行次数加起来再看数量级。因为外层变量成倍变化时外层只执行对数次，内层次数也可能随外层变化。

• ❌ 递归算法没有开数组，空间复杂度就是 $O(1)$O(1)。✅ 递归要计入系统栈，空间复杂度至少与递归深度同阶。因为每层调用都要保存参数、局部变量和返回地址。

• ❌ 顺序表删除第 i 个元素要移动 $n - i + 1$n−i+1 个元素。✅ 删除移动 $n - i$n−i 个，插入才移动 $n - i + 1$n−i+1 个。因为插入位置可以是表尾之后，范围多一个。

• ❌ 在 p 之后插入 s 时，先写 p->next = s。✅ 先让 s 接上 p 原来的后继，再把 s 挂到 p 后面。因为先改 p 的指针，原来的后继就找不到了。

• ❌ 链表的存储密度比顺序表高。✅ 链表每个结点要额外存指针，存储密度小于 1。因为指针域不存数据。

例题精讲

例题 1（单项选择）

下列程序段的时间复杂度是（　）

int count = 0;
for (int i = 1; i <= n; i = i * 3)
    for (int j = 0; j < i; j++)
        count++;

A. $O(\log_2 n)$O(log2​n)　　B. $O(n)$O(n)　　C. $O(n\log_2 n)$O(nlog2​n)　　D. $O(n^2)$O(n2)

答案：B

解析：外层 i 依次取 $1, 3, 9, \dots, 3^k$1,3,9,…,3k（$3^k \le n$3k≤n），内层执行 i 次，总次数 $1 + 3 + \dots + 3^k = \dfrac{3^{k+1} - 1}{2} \lt \dfrac{3n}{2}$1+3+⋯+3k=23k+1−1​<23n​，是 $O(n)$O(n)。选 C 是把外层的对数次与内层「最多 n 次」直接相乘；选 D 是见到两层循环就写平方；选 A 只数了外层。

例题 2（算法设计）

设问：顺序表用数组 A[0..n−1] 存放 n 个整数。设计一个时间复杂度 $O(n)$O(n)、空间复杂度 $O(1)$O(1) 的算法，删除表中所有值等于 x 的元素，其余元素保持原来的相对次序，返回新的表长。

答题要点示范：

（1）设计思想：用 k 记录保留下来的元素个数。从头扫描，遇到不等于 x 的元素就放到 A[k]，k 加 1；扫描结束时 k 就是新表长。

（2）算法：

int delete_x(int A[], int n, int x) {
    int k = 0;                 /* 已保留的元素个数 */
    for (int i = 0; i < n; i++) {
        if (A[i] != x) {
            A[k] = A[i];       /* 保留的元素前移到第 k 个位置 */
            k++;
        }
    }
    return k;                  /* 新的表长 */
}

（3）时间复杂度 $O(n)$O(n)（扫描一遍），空间复杂度 $O(1)$O(1)。

点评：如果每找到一个 x 就把后面的元素整体前移一次，最坏要 $O(n^2)$O(n2)。一个读指针 i、一个写指针 k 的双指针写法，每个元素最多搬一次。

例题 3（算法设计）

设问：带头结点的单链表 L，设计空间复杂度 $O(1)$O(1) 的算法把它就地逆置。

答题要点示范：思想是从第一个结点起依次摘下，用头插法重新插到头结点之后。

void reverse(LNode *L) {           /* L 是头结点 */
    LNode *p = L->next, *r;
    L->next = NULL;
    while (p != NULL) {
        r = p->next;               /* 先记下后继，防止断链 */
        p->next = L->next;         /* 头插：p 插到头结点之后 */
        L->next = p;
        p = r;
    }
}

每个结点处理一次，时间复杂度 $O(n)$O(n)，只用了两个指针变量，空间复杂度 $O(1)$O(1)。

点评：循环里第一句必须先保存后继 r，否则改了 p->next 之后，剩下的结点就丢了。

本节小结

• 数据结构三要素：逻辑结构（集合、线性、树形、图状）、存储结构（顺序、链式、索引、散列）、数据的运算。
• 算法五个特性：有穷、确定、可行、输入、输出；时间复杂度看基本语句次数的数量级，递归的空间要算栈深度。
• 顺序表随机存取，插入平均移动 $\dfrac{n}{2}$2n​ 个、删除平均移动 $\dfrac{n-1}{2}$2n−1​ 个；链表插删不移动元素，指针操作先连后断。
• 算法设计题三段：设计思想、C 代码加注释、时间和空间复杂度；先保底、再优化。