1.0 开篇——数据结构在学什么？#

数据结构在学什么？

• 如何用程序代码把现实世界的问题信息化；
• 如何用计算机高效地处理这些信息从而创造价值。

人类文明三次浪潮（阿尔文·托夫勒《第三次浪潮》）：

托夫勒：“唯一可以确定的是，明天会使我们所有人大吃一惊。”

“信息化”：把现实事物用计算机表示。

学完 C 语言后，如何用计算机表示这些信息、并高效处理 → 这就是数据结构要解决的问题。

计算机系统分层（信息化世界）：一台计算机/手机 = 计组（硬件） → 操作系统 → C、数据结构（软件）；多台计算机之间通过计算机网络互联，构成”信息化世界”。

1.1 数据结构的基本概念#

学习建议：概念多但较基础，抓大放小、形成框架。讨论一种数据结构时，关注”三要素”。

知识总览：

graph LR
    V[数据结构] --> A[基本概念]
    V --> B[三要素]
    A --> A1[数据]
    A --> A2[数据元素、数据项]
    A --> A3[数据对象、数据结构]
    A --> A4[数据类型、抽象数据类型 ADT]
    B --> B1[逻辑结构]
    B --> B2[物理结构（存储结构）]
    B --> B3[数据的运算]

graph LR
    L[逻辑结构] --> A[集合]
    L --> B[线性结构]
    L --> C[树形结构]
    L --> D[图状结构]

1.2.1 算法的基本概念#

什么是算法？

• 程序 = 数据结构 + 算法（数据结构是要处理的信息；算法是处理信息的步骤）。
• 算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列，其中的每条指令表示一个或多个操作。
• 例：做番茄炒蛋（食材+步骤）；对线性表按年龄递增排序（选择排序 Step1~Step4）。

程序设计 = 设计一个好的数据结构 + 设计一个好的算法。

算法的五个特性：

注：算法必须是有穷的，而程序可以是无穷的（如微信是程序，不是算法）。

“好”算法的特质（设计时要尽量追求的目标）：

1. 正确性：能正确地解决求解问题。
2. 可读性：描述要让别人看得懂（可由代码/伪代码/文字描述，重要的是无歧义）。
3. 健壮性：输入非法数据时能恰当地反应或处理，不产生莫名其妙的输出。
4. 高效率与低存储量需求：省时、省内存，即时间复杂度低、空间复杂度低。

1.2.2 算法的时间复杂度#

如何评估算法时间开销？

• 让算法先运行、事后统计运行时间？存在问题：和机器性能、编程语言、编译程序指令质量有关；有些算法不能事后统计（如导弹控制算法）。
• 应事前预估：算法时间复杂度 = 事前预估算法时间开销 $T(n)$ 与问题规模 $n$ 的关系（T 表示 time）。

大 O 表示法：$T(n) = O(f(n))$，表示二者同阶/同等数量级（当 $n \to \infty$ 时二者之比为常数）。只考虑阶数高的部分，系数和低次幂可忽略。

计算规则：

• 加法规则：$T(n) = O(f(n)) + O(g(n)) = O(\max(f(n), g(n)))$ —— 多项相加，只保留最高阶项，系数变为 1。
• 乘法规则：$T(n) = O(f(n)) \times O(g(n)) = O(f(n)\times g(n))$ —— 多项相乘，都保留。

常用技巧：顺序执行的代码只影响常数项（忽略）；只需挑循环中的一个基本操作、分析其执行次数与 n 的关系；多层嵌套循环只需关注最深层循环循环了几次。

三种时间复杂度：

很多算法执行时间与输入数据有关（如顺序查找）；算法性能问题在 n 很大时才会暴露。

如何计算：①找一个基本操作（最深层循环）→ ②分析其执行次数 $x$ 与问题规模 $n$ 的关系 $x=f(n)$ → ③取 $O(x)$ 即 $T(n)$。

例题：

• 逐步递增：int i=1; while(i<=n){ i++; printf(...); } → $T(n)=3n+3=O(n)$。
• 指数递增：i=i*2 每次翻倍 → 最深层循环语句频度 $x$，结束时 $2^x>n$，$x=\log_2 n+1$ → $T(n)=O(\log_2 n)$。
• 顺序查找（数组中找元素 n）：最好 $O(1)$、最坏 $O(n)$、平均 $\frac{1+2+\dots+n}{n}=\frac{1+n}{2}$ → $O(n)$。

常见复杂度排序（口诀”常对幂指阶”）：

$O(1) < O(\log_2 n) < O(n) < O(n\log_2 n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$

1.2.3 算法的空间复杂度#

空间复杂度：空间开销（内存开销）与问题规模 $n$ 的关系，记作 $S(n) = O(f(n))$（S 表示 Space）。

程序运行时的内存需求：

• 程序代码：大小固定，与问题规模无关；
• 数据：局部变量、参数等，其中与 $n$ 相关的变量才影响空间复杂度。

原地工作：算法所需内存空间为常量，即 $S(n) = O(1)$。（如算法1 逐步递增型爱你，无论 $n$ 怎么变，内存都是固定常量。）

例题：

递归的空间复杂度 = 递归调用的深度（若各层所需存储空间不同，分析方法略有区别）。

如何计算空间复杂度：

• 普通程序：①找到所占空间大小与问题规模相关的变量 → ②分析其所占空间 $x$ 与 $n$ 的关系 $x=f(n)$ → ③取 $O(x)$ 即 $S(n)$；
• 递归程序：找到递归调用的深度 $x$ 与 $n$ 的关系，取 $O(x)$ 即 $S(n)$。

常用技巧：同时间复杂度，加法/乘法规则、“常对幂指阶”（$O(1)<O(\log_2 n)<O(n)<O(n\log_2 n)<O(n^2)<O(n^3)<O(2^n)<O(n!)$）。

小结#

1. 基本概念：数据、数据元素/数据项、数据对象/数据结构、数据类型/抽象数据类型 ADT。
2. 数据结构的三要素：逻辑结构（集合/线性/树形/图状，即线性与非线性）、物理结构/存储结构（顺序/链式/索引/散列，后三者非顺序）、数据的运算（定义针对逻辑结构、实现针对存储结构）。
3. 算法：程序 = 数据结构 + 算法；算法的五个特性（有穷性、确定性、可行性、输入、输出），“好”算法特质（正确、可读、健壮、高效低存储）。
4. 时间复杂度：$T(n)=O(f(n))$；加法/乘法规则；“常对幂指阶”；最好/最坏/平均。
5. 空间复杂度：$S(n)=O(f(n))$；原地工作 $O(1)$；递归空间 = 递归深度。
6. 主考点：定义了一个 ADT 就是定义了一个数据结构；存储结构影响运算实现；复杂度用大 O 只留最高阶。

2.1 线性表的定义和基本操作#

线性表（Linear List）定义：是具有相同数据类型的 $n$（$n\ge0$）个数据元素的有限序列。$n$ 为表长，$n=0$ 时是空表。用 $L$ 命名线性表，一般表示为：

$L = (a_1,\ a_2,\ \dots,\ a_i,\ a_{i+1},\ \dots,\ a_n)$

特性：①元素个数有限；②元素类型相同（每个元素所占空间一样大）；③元素有次序。

重要术语：

• $a_i$ 是线性表中的”第 $i$ 个”元素——线性表中的位序（从 1 开始，注意数组下标从 0 开始，用数组实现线性表时要审题）。
• $a_1$ 是表头元素，$a_n$ 是表尾元素。
• 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

Eg：所有整数按递增次序排列，是线性表吗？——否（无限序列，不是线性表）。

graph LR
    A1[a1] --> A2[a2] --> A3[a3] --> A4[a4] --> A5[a5]

基本操作（记忆思路：创销、增删改查）：

为什么要实现基本操作：①团队合作编程，定义的 ADT 要让人方便使用（封装）；②将常用操作封装成函数，避免重复工作、降低出错风险。 改、查（本质是”定位”）：改之前也要先”查”（LocateElem / GetElem）。

什么时候要传入参数的引用 &：对参数的修改结果需要”带回来”时。如 InitList(&L)、DestroyList(&L)、ListInsert(&L,i,e)、ListDelete(&L,i,&e)；而 LocateElem(L,e)、GetElem(L,i) 只读，不加 &。

1
void test(int &x){ x = 1024; ... }   // 引用传递，x 的修改"带回来了"
2
int x = 1;  test(x);                 // 调用后 x=1024

Tips：比起学会”How”，更重要的是想明白”Why”；函数命名要有可读性。

2.2.1 顺序表的定义#

顺序表：用顺序存储的方式实现线性表。顺序存储把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。（即用”数组”存放数据元素。）

元素地址：设线性表第一个元素存放位置为 LOC(L)（location 的缩写），则第 $i$ 个元素地址 = LOC(L) + $(i-1)\times$ sizeof(ElemType)。用 C 语言 sizeof(ElemType) 得到元素大小（如 sizeof(int)=4B，sizeof(Customer)=8B）。

顺序表的实现——静态分配：

1
#define MaxSize 10                 // 定义最大长度
2
typedef struct {
3
    ElemType data[MaxSize];        // 用静态的"数组"存放数据元素
4
    int length;                    // 顺序表的当前长度
5
} SqList;                          // 顺序表类型定义（静态分配）

Sq = sequence（顺序、序列）。给数据元素分配连续存储空间，大小为 MaxSize × sizeof(ElemType)。

• 表长一开始就确定、无法更改（静态）。存满就”放弃治疗”；若一开始就声明很大的空间，又会浪费。

顺序表的实现——动态分配（静态数组存满无法扩容，用动态数组）：

1
#define InitSize 10
2
typedef struct {
3
    ElemType *data;    // 指示动态分配数组的指针
4
    int MaxSize;       // 顺序表的最大容量
5
    int length;        // 顺序表的当前长度
6
} SeqList;             // 动态分配方式

1
L.data = (ElemType *) malloc(sizeof(ElemType) * InitSize);   // 申请一片连续空间

• C 用 malloc / free（头文件 <stdlib.h>），C++ 用 new / delete。
• 动态扩容（IncreaseSize(&L, len)）：int *p = L.data; L.data = (int *) malloc((L.MaxSize + len) * sizeof(int)); for(...) L.data[i]=p[i]; L.MaxSize += len; free(p);
• 注：可用 realloc 实现，但建议初学者用 malloc / free 以理解过程；扩容要把旧数据复制到新区域，时间开销大（O(n)）。

顺序表的特点：

2.2.2_1 顺序表的插入和删除#

插入：ListInsert(&L, i, e) —— 在表 L 的第 i 个位置插入元素 e。

1
bool ListInsert(SqList &L, int i, int e){
2
    if(i < 1 || i > L.length + 1) return false;   // 判断 i 的范围是否有效
3
    if(L.length >= MaxSize) return false;          // 当前存储空间已满，不能插入
4
    for(int j = L.length; j >= i; j--)             // 将第 i 个元素及之后的元素后移
5
        L.data[j] = L.data[j-1];
6
    L.data[i-1] = e;                               // 在位置 i 处放入 e
7
    L.length++;                                     // 长度 +1
8
    return true;
9
}

• 注意位序 i 与数组下标关系：元素后移时从表尾元素开始往前移动。
• 健壮性：if 判断 i 是否合法、空间是否已满，返回 bool 给使用者反馈。

插入时间复杂度（问题规模 n = L.length）：

删除：ListDelete(&L, i, &e) —— 删除表 L 第 i 个位置的元素，并用 e 返回其值。

1
bool ListDelete(SqList &L, int i, int &e){
2
    if(i < 1 || i > L.length) return false;   // 判断 i 的范围是否有效
3
    e = L.data[i-1];                           // 将被删除的元素赋值给 e
4
    for(int j = i; j < L.length; j++)          // 将第 i 个位置后的元素前移
5
        L.data[j-1] = L.data[j];
6
    L.length--;                                 // 长度 -1
7
    return true;
8
}

• 元素前移时从靠前的元素开始（与插入的后移相反，注意别弄反）。
• e 加了 &，因为要把删除的值”带回来”；不加 & 传的是复制品，改不回去。

删除时间复杂度（问题规模 n = L.length）：

2.2.2_2 顺序表的查找#

按位查找：GetElem(L, i) —— 获取表 L 第 i 个位置的元素的值。

1
ElemType GetElem(SeqList L, int i){
2
    return L.data[i-1];      // 位序 i 对应数组下标 i-1
3
}

• 时间复杂度 $O(1)$：顺序表数据元素在内存中连续存放，根据起始地址 + 元素大小可立即定位第 i 个元素（随机存取特性）。
• 指针类型决定”步长”：data[i] = 起始地址 + i×sizeof(ElemType)；malloc 返回 void*，需强制转换成 ElemType*。

按值查找：LocateElem(L, e) —— 在表 L 中查找第一个元素值等于 e 的元素，返回其位序（找不到返回 0）。

1
int LocateElem(SeqList L, ElemType e){
2
    for(int i = 0; i < L.length; i++)
3
        if(L.data[i] == e)  return i + 1;   // 数组下标 i 对应位序 i+1
4
    return 0;                               // 退出循环，查找失败
5
}

• 基本数据类型（int、char、double、float…）可直接用 == 比较；
• 结构类型不能直接用 ==（C 语言会报错），需逐分量比较，或封装成 isCustomerEqual(a, b) 函数；考研初试手写代码可直接用 ==（主要考算法思想）。

按值查找时间复杂度（问题规模 n = L.length）：

2.3.1 单链表的定义#

单链表：用链式存储（存储结构）实现了线性结构（逻辑结构）。每个结点存储一个数据元素，各结点间的先后关系用一个指针表示。

graph LR
    H[头指针 L] --> N1[a1] --> N2[a2] --> N3[a3] --> N4[a4] --> N5[NULL]

用代码定义一个单链表：

1
typedef struct LNode{      // 定义单链表结点类型
2
    ElemType data;         // 数据域，存放一个数据元素
3
    struct LNode *next;    // 指针域，指向下一个结点
4
}LNode, *LinkList;

• typedef <数据类型> <别名>：给类型重命名。LNode 是结点类型，LinkList 等价于 LNode *。前者强调”是一个结点”，后者强调”这是一个单链表”，合适的地方用合适的名字可读性更高。
• 新建结点：LNode * p = (LNode *) malloc(sizeof(LNode));（malloc 返回 void*，需强制转换）。

两种实现方式：带头结点 / 不带头结点（头结点不存放数据，只是为了操作方便）：

头指针 L 就代表整个单链表；因为要修改头指针，InitList 的参数要加 & 引用。

2.3.2_1 单链表的插入和删除#

插入：

① 按位序插入 ListInsert(&L, i, e)：在第 i 个位置插入元素 e，核心是找到第 i-1 个结点，把新结点插到它后面。

1
bool ListInsert(LinkList &L, int i, ElemType e){
2
    if(i < 1) return false;
3
    LNode *p; int j = 0;
4
    p = L;                                // 头结点看作第 0 个结点
5
    while(p != NULL && j < i-1){ p = p->next; j++; }   // 找到第 i-1 个结点
6
    if(p == NULL) return false;
7
    LNode *s = (LNode *) malloc(sizeof(LNode));
8
    s->data = e;
9
    s->next = p->next;                    // 先连（顺序不能颠倒）
10
    p->next = s;                          // 再断
11
    return true;
12
}

• 时间复杂度：最好 $O(1)$（插表头 i=1），最坏 $O(n)$（插表尾），平均 $O(n)$。
• 不带头结点：不存在”第 0 个”结点，i=1 需特殊处理（改头指针 L）。

② 指定结点的后插 InsertNextNode(p, e)：s->next = p->next; p->next = s; —— $O(1)$。

③ 指定结点的前插 InsertPriorNode(p, e)：偷天换日——把新结点 s 插到 p 后面，再交换数据，$O(1)$：

1
s->next = p->next; p->next = s;
2
s->data = p->data;      // 把 p 中元素复制到 s
3
p->data = e;            // p 覆盖为 e

删除：

① 按位序删除 ListDelete(&L, i, &e)：找到第 i-1 个结点，令其指向第 i+1 个结点，释放第 i 个结点。

1
bool ListDelete(LinkList &L, int i, ElemType &e){
2
    if(i < 1) return false;
3
    LNode *p; int j = 0; p = L;
4
    while(p != NULL && j < i-1){ p = p->next; j++; }
5
    if(p == NULL) return false;
6
    if(p->next == NULL) return false;      // 第 i-1 个结点之后已无其余结点
7
    LNode *q = p->next;
8
    e = q->data;
9
    p->next = q->next;                     // 将 *q 从链中"断开"
10
    free(q);
11
    return true;
12
}

• 时间复杂度：最好 $O(1)$（删表头），最坏/平均 $O(n)$。

② 指定结点的删除 DeleteNode(p)：

• 方法 1：传入头指针，循环找到 p 的前驱，改前驱的 next。
• 方法 2：偷天换日——把 p->next 的数据复制到 p，再删除 p->next，$O(1)$。

  有坑：p 是最后一个结点时（p->next == NULL），方法 2 要特殊处理。

Tips：这些代码都要会写；注意审题（带头否？）；体会”封装”的好处。

2.3.2_2 单链表的查找#

按位查找 GetElem(L, i)：返回第 i 个结点（头结点看作第 0 个结点）。

1
LNode * GetElem(LinkList L, int i){
2
    if(i < 0) return NULL;
3
    LNode *p; int j = 0;
4
    p = L;                                       // 头结点为第 0 个结点
5
    while(p != NULL && j < i){ p = p->next; j++; }
6
    return p;                                     // i 超过表长时返回 NULL
7
}

• 时间复杂度 $O(n)$：[单链表不具备”随机访问”特性，只能依次扫描]（对比顺序表是 $O(1)$）。
• 王道书版本用 j=1; p=L->next；if(i==0) return L; if(i<1) return NULL;。

按值查找 LocateElem(L, e)：返回第一个数据域等于 e 的结点指针，找不到返回 NULL。

1
LNode * LocateElem(LinkList L, ElemType e){
2
    LNode *p = L->next;                          // 从第 1 个结点开始查找
3
    while(p != NULL && p->data != e) p = p->next;
4
    return p;
5
}

• 平均时间复杂度 $O(n)$。（ElemType 是复杂结构类型时需逐分量比较，同顺序表。）

求单链表长度 Length(L)：

1
int Length(LinkList L){
2
    int len = 0; LNode *p = L;
3
    while(p->next != NULL){ p = p->next; len++; }
4
    return len;
5
}

• 时间复杂度 $O(n)$。

对比：顺序表可”随机存取”（$O(1)$ 按位访问）；单链表只能依次扫描，三种基本操作（按位插入/删除/查找）平均都是 $O(n)$。写循环扫描时要注意边界条件。