引论与 C 语言基础

你半年前学到了指针、结构体、结构体函数，现在大概忘了不少。数据结构这门课，80% 的代码痛苦都来自指针没吃透。所以我们先花点功夫把这块地基夯实，后面所有链表、树、图的代码才不会一看就懵。这一章你务必读透，它不是复习，是后面一切的钥匙。

1.1 内存、变量、地址：先建立物理图像

写代码前，脑子里要有一张「内存」的图像。你可以把内存想象成一条非常长的储物柜走廊，每个柜子大小一样（1 字节 = 8 个比特），每个柜子都有一个唯一的编号，这个编号就叫地址（address）。

当你写 int x = 10; 的时候，发生了两件事：

1. 系统在走廊里找一块连续的空地（int 通常占 4 个柜子，即 4 字节），把它「划给」名字 x。
2. 往这块地里写进了数字 10。

所以一个变量同时有两个属性：它的值（这里是 10），和它的地址（它占的那块地的起始编号，比如 0x7ffe1234）。这两者千万别混。日常我们用名字 x 操作值，但底层一切都是靠地址在干活。

int x = 10;
printf("x 的值是 %d\n", x);      // 取 x 的值 -> 10
printf("x 的地址是 %p\n", &x);   // & 是"取地址"运算符 -> 类似 0x7ffe1234

记住这个运算符：& 读作「取地址」，放在变量前面，得到这个变量住在哪儿。

1.2 指针：一个专门用来存「地址」的变量

普通变量存的是值（10、3.14、'A'）。指针变量存的是「地址」——也就是别的变量住在哪儿。就这么简单，别被它吓到。

int x = 10;
int *p = &x;   // p 是一个指针,它存的是 x 的地址。读作:p 指向 x

int *p 这个写法拆开看：p 是变量名，int * 是它的类型，意思是「一个指向 int 的指针」。* 在定义的时候表示「这是个指针」。

定义好之后，* 还有第二个用途——解引用（dereference），也就是「顺着这个地址，去把那块地里的值拿出来/改掉」：

int x = 10;
int *p = &x;     // p 指向 x

printf("%d\n", *p);   // *p 的意思:顺着 p 存的地址走过去,取出那里的值 -> 10
*p = 99;              // 顺着 p 走过去,把那块地的值改成 99
printf("%d\n", x);    // x 现在是 99!因为 p 指向的就是 x 那块地

这是指针的全部威力所在：通过指针 p，你能间接地修改它指向的那个变量 x，哪怕你手上只有 p 没有 x 的名字。把这一点想透，后面链表「改指针」的所有操作都顺了。

一句口诀帮你记 * 和 & 的关系：& 把值变地址，* 把地址变值，它们是一对反操作。*&x 等于 x。

1.2.1 空指针 NULL

有时一个指针「暂时不指向任何东西」，我们让它等于 NULL（本质是地址 0，表示「无效、空」）。链表的末尾就是用 NULL 来表示「后面没有了」。永远不要对 NULL 指针解引用（*p 当 p 是 NULL），程序会直接崩溃——这是初学者最常见的 bug。

1.3 结构体：把几个相关的数据捆成一个整体

现实里的「一个学生」有学号、姓名、成绩，它们应该绑在一起。结构体（struct）就是干这个的——它让你自定义一种新的数据类型，里面打包若干个字段。

struct Student {
    int   id;        // 学号
    char  name[20];  // 姓名
    float score;     // 成绩
};                   // 注意这个分号,初学者老是漏

struct Student s;        // 定义一个学生变量 s
s.id = 1001;             // 用 . (点) 访问它的字段
s.score = 88.5;

1.3.1 typedef：给类型起个简短的别名（本课大量使用）

每次都写 struct Student 太啰嗦。typedef 能给类型起别名，让代码清爽。本课所有数据结构都用这个套路定义，你会反复见到：

typedef struct Student {
    int   id;
    char  name[20];
    float score;
} Student;     // 从此 Student 就等价于 struct Student

Student s;     // 不用再写 struct 了

还有一个本课的关键约定——ElemType。我们写数据结构时，往往不关心存的到底是 int 还是 float，只想说「存的是某种元素」。于是开头来一句：

typedef int ElemType;   // 本课约定:元素类型先当 int。以后要存别的,只改这一行

后面代码里凡是元素，都写 ElemType。这样整套结构换个元素类型只需改一行，是一种朴素的「泛型」手段。看到 ElemType 你就理解成「数据元素的类型，这里碰巧是 int」即可。

1.4 结构体指针与 ->（链表的命根子）

当你有一个指向结构体的指针，想访问它的字段，按理要写 (*p).id（先解引用拿到结构体，再用点访问）。但这太丑，C 提供了专门的箭头运算符 ->：

Student s;
Student *p = &s;

(*p).id = 1001;   // 能用,但难看
p->id = 1001;     // 完全等价,推荐!读作"p 指向的那个结构体的 id 字段"

p->字段 就是「顺着指针 p，访问它指向的结构体的某个字段」。链表的节点全是用指针操作的，所以 -> 会出现成百上千次，现在就把它焊进肌肉记忆。

1.5 动态内存：malloc 与 free（链表节点从哪来）

前面 int x; 这种变量，是编译器在栈上自动分配的，函数一结束就自动回收，大小也得编译时定死。但链表是「用一个加一个，运行时才知道要几个」，这就需要手动、动态地向系统申请内存。这块手动管理的内存区域叫堆（heap）。

两个函数：

• malloc(n)：向系统申请 n 字节的连续内存，返回这块内存的起始地址（一个指针）。申请失败返回 NULL。
• free(p)：把 p 指向的那块内存还给系统。你 malloc 的，必须自己 free，否则内存泄漏。

#include <stdlib.h>   // malloc/free 在这个头文件里

// 申请一个能装下 Student 的内存,返回它的地址,存进指针 p
Student *p = (Student *)malloc(sizeof(Student));
//          ^^^^^^^^^^          ^^^^^^^^^^^^^^^^
//          强制类型转换         sizeof 自动算出 Student 占多少字节,别手写数字

if (p == NULL) {            // 好习惯:永远检查是否申请成功
    printf("内存不够了!\n");
    exit(1);
}

p->id = 1001;              // 用 -> 操作这块新内存
p->score = 90;

free(p);                  // 用完归还
p = NULL;                 // 好习惯:free 之后把指针置空,防止误用"野指针"

sizeof(类型) 会自动算出该类型占多少字节，永远用 sizeof(Student) 而不要手写 28——不同机器大小可能不同，手写数字迟早出错。

这门课你会无数次写 malloc(sizeof(节点类型)) 来「新建一个节点」，再用 free 删除节点。把这两句当成「出生」和「死亡」记住。

1.6 函数传参：传值 vs 传址（为什么有的改了没用）

这是初学者最大的坑，必须讲透。C 的函数传参默认是「传值」——把实参复制一份给形参，函数里改的是那个副本，外面原件纹丝不动。

void addOne(int a) {   // a 是外面那个数的"复印件"
    a = a + 1;         // 改的是复印件
}
int main() {
    int x = 5;
    addOne(x);
    printf("%d\n", x);  // 还是 5!因为函数改的是副本
}

想让函数真正改到外面的变量，必须把变量的地址传进去（传址），函数内通过指针解引用去改原件：

void addOne(int *a) {   // a 是一个指针,存着外面变量的地址
    *a = *a + 1;        // 顺着地址,改的是原件
}
int main() {
    int x = 5;
    addOne(&x);         // 传地址进去
    printf("%d\n", x);  // 6!真的改到了
}

这个规律推广到数据结构里极其重要：如果一个函数要改动链表的头指针、要改顺序表的长度，就必须把那个东西的地址传进去（也就是「指针的指针」**，后面线性表代码会见到 LinkList *L）。看到双星号别慌，它就是「想在函数里改掉外面那个指针本身」的意思。

C++ 的「引用」& 能让这件事写起来更舒服，但你只会 C，我们就先用 C 的指针传址。等真正写到非用引用不可的地方，我再给你打补丁。

1.7 数组与指针的暧昧关系

数组名 a 在大多数场合会「退化」成指向它第一个元素的指针。所以 a[i] 本质等价于 *(a + i)——从首地址往后挪 i 个位置再取值。这解释了为什么数组下标从 0 开始（第 0 个元素就在首地址，偏移 0），也解释了为什么数组随机访问是 O(1)：知道首地址和下标，一次乘加就算出地址，直接取，跟数组多大无关。这个事实是第 2 章顺序表的理论基础，记住它。

1.8 C 基础自测

1. int x = 5; int *p = &x; *p = 8; 之后 x 是几？为什么？
2. & 和 * 分别是什么意思？*&x 等于什么？
3. p->id 和 (*p).id 是什么关系？
4. 为什么 void f(int a){ a=1; } 改不到外面的变量？要怎么改才行？
5. malloc(sizeof(Student)) 返回的是什么？用完为什么要 free？
6. 为什么数组随机访问 a[i] 是 O(1)？

1.9 这门课到底在研究什么

一句话本质：数据结构研究的是「怎么把一堆数据组织、存放在计算机里，让你最关心的那些操作（查、增、删、遍历）跑得最快、最省空间」。

为什么需要专门研究这个？因为同样一堆数据，摆放方式不同，操作的快慢能差出天壤之别。举个直观例子：图书馆有十万本书。如果随便堆在地上（无组织），找一本书要翻遍十万本；如果按编号上架（有组织），顺着编号几步就找到。数据在内存里也一样——组织方式决定了效率。这门课就是系统地研究各种「组织方式」（叫数据结构）以及在它们上面「怎么操作」（叫算法）。

所以这门课有两条腿：数据结构（数据怎么组织）和算法（怎么在这种组织上高效干活），合称「数据结构与算法」。

1.10 三个基本概念：数据、数据元素、数据项

这三个是教材开篇必给的定义，考试爱考填空/选择，理解层级关系即可：

• 数据（Data）：能被计算机处理的一切信息的总称（数字、文字、图像、声音……）。
• 数据元素（Data Element）：数据的基本单位，通常作为一个整体来处理。比如学生表里的「一个学生」就是一个数据元素。也叫记录（record）或节点（node）。
• 数据项（Data Item）：构成数据元素的最小单位，不可再分。比如一个学生（数据元素）由学号、姓名、成绩这些数据项组成。

层级关系一句话：数据 ⊃ 数据元素 ⊃ 数据项。打个比方，一张 Excel 表是「数据」，每一行是一个「数据元素」，每个单元格是一个「数据项」。

1.11 两种结构：逻辑结构 vs 存储结构（全课的总纲）

这是整门课最重要的一对概念，所有章节都在这个框架里打转，务必吃透。

1.11.1 逻辑结构：数据元素之间「关系」的抽象

逻辑结构只关心「数据元素之间是什么关系」，不管它在内存里怎么存。它是站在人/问题的角度看数据。一共四类：

1. 集合结构：元素之间除了「同属一个集合」再无任何关系，一盘散沙。（用得少）
2. 线性结构：元素排成一条队，一个挨一个，每个元素最多一个前驱、一个后继。典型：线性表、栈、队列、串。（1 对 1）
3. 树形结构：元素之间是一对多的层次关系，一个「父」可以有多个「子」。典型：二叉树、各种树。（1 对多）
4. 图状结构（网状结构）：元素之间多对多，谁都能和谁有关系。典型：图。（多对多）

整本书的剧情主线就是逻辑结构由简到繁：线性(1对1) → 树(1对多) → 图(多对多)。 你现在能在脑子里画出这条线，就抓住了全课的骨架。

1.11.2 存储结构（物理结构）：逻辑结构在内存里「怎么落地」

同一个逻辑结构，可以用不同方式真正存到内存里。这是站在计算机的角度。主要两种（外加两种衍生）：

1. 顺序存储：把元素存在一块连续的内存里（就是数组）。元素的逻辑先后关系，靠物理位置相邻来体现——你前一个，地址就在我前面。

   • 优点：能随机访问（地址 = 首地址 + 下标 × 元素大小，O(1) 直达）。
   • 缺点：中间插入/删除要挪动大量元素；大小往往要预先定好。

2. 链式存储：元素散落在内存各处，每个元素额外存一个「指针」指向下一个元素的地址，靠指针把它们串起来。逻辑上相邻的两个元素，物理上可能离得很远。

   • 优点：插入/删除只改几个指针，不用挪动数据；想多大就多大。
   • 缺点：不能随机访问，找第 k 个得从头顺着指针数过去；每个元素要额外花空间存指针。

3. 索引存储：在数据之外，额外建一张「目录（索引表）」，记录每个/每组元素的存放地址，查找时先查目录再定位。（像书的目录）

4. 散列存储（哈希）：用一个公式（哈希函数）直接由「数据的值」算出它该存的地址。查找时再用同一公式算地址直达，平均 O(1)。（第 7 章细讲）

核心认知（请刻进脑子）：逻辑结构是「数据之间的关系，由问题决定」，存储结构是「在内存里的实现方式，由我们选择」。同一种逻辑结构（比如线性表），既能用顺序存储（顺序表），也能用链式存储（链表）。 这门课的每一章，基本都是「先讲一种逻辑结构，再分别讲它的顺序实现和链式实现，比较优劣」。你带着这个模板去读每一章，就不会乱。

1.12 抽象数据类型 ADT

抽象数据类型（Abstract Data Type, ADT） = 一种数据的逻辑结构 + 在它上面能做的一组操作，但只说「能做什么」，不说「怎么实现」。

打个比方：一台自动售货机对你的「ADT」就是「投币 → 选商品 → 出货」这几个操作，你不需要知道里面机械结构怎么运转。ADT 就是这种「只暴露操作接口，隐藏内部实现」的思想。它的好处是把「用」和「实现」分开：用的人只管调操作，实现的人可以随便换底层（顺序存储换成链式存储），不影响使用者。

本课里你会看到一种半形式化的 ADT 定义写法，比如：

ADT 线性表(List)
  数据对象: D = { a1, a2, ..., an }  // 装的是什么
  数据关系: 每个 ai 的后继是 a(i+1)   // 元素间什么关系
  基本操作:
     InitList(&L)      初始化空表
     ListInsert(&L,i,e) 在第 i 个位置插入 e
     ListDelete(&L,i,&e) 删除第 i 个元素
     GetElem(L,i,&e)    取第 i 个元素
     ListLength(L)      求表长
     ......

考试里 ADT 定义一般不要你死背格式，理解「ADT = 逻辑结构 + 操作集合，且实现无关」这个思想即可。

1.13 算法及其五大特性

算法（Algorithm）= 解决某个问题的、一步步的、明确的操作序列。 通俗说就是「办事的步骤/菜谱」。一个合格的算法必须满足五个特性（高频考点，建议记住）：

1. 有穷性：必须在有限步内结束，不能死循环。（这是「算法」和「程序」的关键区别之一——死循环的程序不是算法）
2. 确定性：每一步都有确切含义，无歧义，相同输入必得相同输出。
3. 可行性：每一步都能用基本操作有限次实现，真的做得出来。
4. 输入：有零个或多个输入。（可以没有输入，比如打印固定内容）
5. 输出：有一个或多个输出。（必须有结果，否则白算）

衡量一个算法好不好，主要看两个维度：时间效率（跑得快不快）和空间效率（占内存多不多）。还有正确性、可读性、健壮性等，但考试核心是时间和空间，下面专门讲。

1.14 算法分析：时间复杂度（全课的标尺，必考）

1.14.1 为什么不直接测运行秒数

你可能想：跑一遍掐秒表不就知道快慢了？不行。同一个算法，在快电脑上 1 秒、慢电脑上 10 秒；输入 100 个数和输入 100 万个数差别巨大。我们想要一个与机器无关、只反映算法本身好坏、且能看出数据量变大时趋势的衡量方式。这就是时间复杂度。

1.14.2 核心思想：数「基本操作」执行多少次，看它随 n 怎么增长

我们不数秒，而是数算法里「基本操作」执行的次数，把它写成数据规模 n 的函数 T(n)。然后我们只关心 n 很大时 T(n) 的增长趋势，因为数据小的时候谁都快，数据大才见真章。

1.14.3 大 O 记号

大 O 记号 O(...) 就是用来描述这个「增长趋势」的。规则极简单，两步：

1. 只保留最高阶项（n 很大时，低阶项的贡献可以忽略）。
2. 去掉最高阶项的系数（系数只反映常数倍快慢，不影响增长「档次」）。

例子：

T(n) = 3n² + 5n + 100   →   O(n²)
（n 很大时,n² 远远压倒 5n 和 100;系数 3 也不影响"是二次增长"这个本质）

T(n) = 2n + 1000         →   O(n)
T(n) = 7                 →   O(1)    常数,不随 n 变

1.14.4 怎么从代码里数出复杂度（实操技巧，必须会）

• 顺序执行的几段代码：取其中复杂度最高的那段。（O(n) 后面接 O(n²)，总的是 O(n²)）

• 单层循环，循环次数和 n 成正比 → O(n)。

  for (int i = 0; i < n; i++)  // 执行 n 次
      sum += a[i];             // 里面是 O(1) 操作
  // 总共 O(n)

• 两层嵌套循环，各跑 n 次 → O(n²)。三层嵌套 → O(n³)。

  for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)   // 外 n 次,每次内又 n 次
          x++;                       // n×n = n² 次
  // 总共 O(n²)

• 循环变量「翻倍」或「折半」 → O(log n)。这是个关键模式，一定要认得：

  for (int i = 1; i < n; i = i * 2)  // i: 1,2,4,8,16... 翻倍增长
      x++;
  // i 翻倍多少次到 n? 答案是 log₂n 次,所以是 O(log n)

  直觉：每次把规模砍一半（或翻一倍），很快就到头。二分查找、树的高度都是这个道理。「不断对半」就是 log。

• 递归：用「递归次数 × 每次的工作量」估算，或画递归树。比如「把问题分成两半、分别解决再合并」的归并/快排，是 O(n log n)（log n 层，每层总工作量 O(n)）。

1.14.5 常见复杂度从快到慢（背下来，这是基本盘）

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
 常数   对数      线性    线性对数      平方    立方    指数    阶乘

直观感受它们的差距：当 n = 1,000,000 时，O(log n) ≈ 20，O(n) = 一百万，O(n²) = 一万亿（已经跑不动了），O(2ⁿ) 则是宇宙都算不完。所以从 O(n²) 优化到 O(n log n) 不是锦上添花，是从「能用」到「不能用」的分界。 这也是后面学各种高级结构的根本动机。

1.14.6 最好、最坏、平均情况（高频考点，必须分清）

同一个算法，对不同的输入数据，操作次数可能差很多。所以复杂度要分三种情况说：

• 最好情况：运气最好时的复杂度。
• 最坏情况：运气最差时的复杂度（最常用，因为它给出性能的保证上界）。
• 平均情况：所有可能输入的期望复杂度。

经典例子——在长度 n 的数组里顺序查找某个数：

• 最好：第一个就是它，比较 1 次 → O(1)。
• 最坏：在最后一个，或根本不存在，比较 n 次 → O(n)。
• 平均：假设它等概率出现在任意位置，平均比较 (n+1)/2 次 → O(n)。

考试常问「XX 算法的平均/最坏时间复杂度是多少」，务必能分别说出来，别只记一个。

1.15 算法分析：空间复杂度

空间复杂度衡量算法运行时额外需要的内存（不算输入数据本身占的），同样用大 O 表示。

• 如果只用了几个临时变量，跟 n 无关 → O(1)，叫原地（in-place）算法。
• 如果额外开了一个和输入一样大的数组 → O(n)。
• 递归算法别忘了算「递归栈」的空间：每深入一层递归，系统要在栈上保存一层现场。递归深度是多少，空间就是多少。比如递归深度 n 的递归是 O(n) 空间；快排平均递归深度 log n，空间 O(log n)。

时间和空间常常是一对矛盾，能用空间换时间，也能用时间省空间——这又回到了全课的灵魂：权衡（trade-off）。

1.16 全课灵魂：没有最好的结构，只有最合适的

提前把这门课的「世界观」给你，后面每个结构都用它来理解：

访问快和增删快，天生打架；省时间和省空间，也天生打架。

• 数组（顺序存储）：随机访问快 O(1)，但增删要挪动元素 O(n)。
• 链表（链式存储）：增删只改指针快，但访问要从头数 O(n)。
• 树：把访问和增删都压到 O(log n)，是「各退一步」的折中。
• 哈希表：访问和增删平均都 O(1)，代价是丢掉了「有序」并且费空间。

所以考试里只要问「为什么用 X 不用 Y」「X 和 Y 各有什么优缺点」，答案永远是在这条权衡线上比较 trade-off。每学一个结构，都默默问自己一句：它牺牲了什么，换来了什么？ 想通这一点，知识点会自己织成网，而不是一堆孤立的结论。

1.17 导论与复杂度自测

1. 逻辑结构有哪四种？存储结构主要有哪两种？「同一个逻辑结构可以有多种存储结构」举个例子说明。
2. 数据、数据元素、数据项三者的包含关系？
3. 算法的五大特性是什么？为什么死循环不算算法？
4. 把下列函数写成大 O：5n³ + 100n² + 9；2ⁿ + n¹⁰⁰；100。
5. 一段双层嵌套循环、内外都跑 n 次，时间复杂度是多少？for(i=1;i<n;i*=2) 呢？
6. 顺序查找的最好/最坏/平均时间复杂度各是多少？
7. 为什么递归算法要特别考虑空间复杂度？