Code59 零基础 · 第 0 课 · 零基础先修¶

2026-09-14 · 零基础讲解 · 先读题目与条件，再看示例和逐步讲解

这一课不要求你先会指针、递归或复杂度。先认识这些词，再读具体题。每次只弄懂一小段，不必第一次就把所有代码背下来。

返回 59 题总目录

1. 算法是什么：把你的做法写成不会误解的步骤¶

假设要从 6、2、5 中找最小数。你可能一眼看见 2，但计算机需要明确步骤：先暂时记住 6；读到 2，发现更小，改记 2；读到 5，不更小，不改；最后交出记住的 2。

“暂时记住的数”放在变量里，“依次读三个数”写成循环，“更小就替换”写成判断。算法不是先背一串英文，而是先把这条过程说清楚。

2. 变量、数组、下标与长度¶

变量像一个有名字的小格子。int x = 6; 表示申请一个能存整数的格子，名字叫 x，现在放 6。以后 x = 2; 会用 2 覆盖这个格子里的旧值 6。

数组是一排同类型格子：

格子的编号（下标）	0	1	2	3	4
`A` 中存的数	8	3	6	2	9

A[0] 是 8，A[3] 是 2。第 4 个元素的下标是 3。 五个元素的有效下标是 0 到 4，所以最后一个位置为 n-1，不是 n。

“容量”是总共有多少格子；“长度”是现在承认其中多少格子有效。容量 50、长度 3 的顺序表，只把下标 0、1、2 当作表中元素，后面的格子暂不属于有效内容。

因此删除后 length=2 并不要求把原第 3 格擦成 0；它只是不再被当作表中元素。写入 data[length] 可以用于在有空余容量时追加，但不能把它当作一个已有元素来读取。

3. 最常见的符号，先翻译成人话¶

写法	意思	小例子
`x = 3`	把右边结果写入左边	原 x 为 8，执行后为 3
`x == 3`	问 x 是否等于 3，不修改 x	答案只有真或假
`x != 3`	问 x 是否不等于 3	x 为 8 时为真
`<`、`>`	小于、大于	`2<5` 为真
`<=`、`>=`	小于等于、大于等于	`2<=2` 为真
`&&`	两个条件都成立才算真	人到了，并且票有效
`\\|\\|`	至少一个条件成立就算真	没带票，或者票失效
`!flag`	把真假反过来	flag 为 false，则 !flag 为 true
`x++`	使用旧值后，把 x 加 1	单独一行时可看成 x=x+1
`++x`	先把 x 加 1，再使用新值	常用于栈顶从 -1 变 0 后入栈
`x--`	使用旧值后，把 x 减 1	单独一行时可看成 x=x-1
`x += 2`	把 x 改成 x+2	是赋值，不是数学方程
`x % 2`	x 除以 2 的余数	非负整数余 0 为偶数、余 1 为奇数
`a ? b : c`	a 成立就取 b，否则取 c	`x>=0 ? x : -x` 取绝对值

C 的整数除法会舍去小数部分；本书下标非负，5/2 得 2。因此 mid=(low+high)/2 在两格中间时取靠左的格子。

两句非常容易看错的代码¶

A[k++] = B[j++]; 在这里等价于分开写：

A[k] = B[j];  // 先按当前两个下标复制
k = k + 1;    // 下一次往 A 的下一个格子写
j = j + 1;    // 下一次读 B 的下一个格子

例如 k=2、j=0，先执行 A[2]=B[0]，然后 k=3、j=1。不是先加一再复制。这个拆法适用于这里互不混淆的独立下标，别推广成任何带多个自增的 C 表达式都能随意调整顺序。

while (p != NULL && p->next != NULL) 会从左到右判断。如果 p 已经为空，右边不再执行，这叫短路求值，正是它保护我们不去访问空地址。

4. if、for、while、break、return 怎么走¶

if 是岔路：条件真就做它下面的语句；有 else 时，条件假走 else。花括号 {...} 把多句组成一个整体；没花括号时，if 只控制紧接着的一句，不会自动控制下面所有缩进行。

for (int i = 0; i < 3; i++) {
    printf("%d ", i);
}

按这个顺序读：

只在开始时做一次 i=0。
检查 i<3，成立，输出 0。
执行 i++，i 变 1；回到条件，输出 1。
i 变 2；条件成立，输出 2。
i 变 3；条件不成立，退出，不输出 3。

while 是“只要条件成立，就反复做里面的事”。必须想清楚里面哪个动作会让条件最终不成立。例如遍历链表靠 p 一直向后走，最后到 NULL。

break 只跳出当前这一层循环，继续执行循环后面的代码；return 结束当前整个函数，把结果交回调用者。递归中的 return 只结束这一次调用，不是把程序中所有同名调用一起结束。

5. 函数：交给它什么，它交回什么¶

把函数看成一个可重复使用的小任务。int add(int a,int b) 表示收到两个整数，交回一个整数。add(2,3) 是一次调用，形参 a、b 本次分别收到 2、3。

返回类型 int 表示交回整数，bool 表示真假，void 表示不交回一个普通返回值。void 不等于什么都没做：它可能已经改好了数组，或把答案打印到屏幕。

在本题集中，“返回”“打印”“改输出参数”是三件事。例如倒数第 k 题先打印结点值 40，再返回成功标志 1；不能说“返回的答案是 40”。

6. 指针：记的是格子的位置，不是格子里的数¶

先只考虑一个整数：

int x = 7;
int *p = &x;
*p = 9;

&x 是 x 所在的位置。int *p 声明 p 是指向整数的指针；p=&x 让 p 记住 x 的位置。表达式中的 *p 是沿 p 找到的那个整数格子。因此 *p=9 改的是 x，执行后 x 为 9。

星号有不同语境：声明 int *p 中，它说明类型；表达式 *p 中，它表示沿地址访问；a*b 中，它又是乘法。不要只看到星号就当乘法。

函数若要修改调用者的整数，可以接收地址：int *count。调用时传 &count，函数内部用 (*count)++ 修改外面的计数。括号很重要：(*count)++ 增加的是被指向的整数，不是让指针移到别的位置。

NULL 是空指针，意思是“没有指向任何有效对象”。它不是一个普通数据结点，也不是一个值为 0 的结点。不能读 NULL->next，就像不能到一个不存在的房间去找下一间房。

7. 结构体、点号与箭头¶

结构体是把相关字段装成一包。例如顺序表既要有数组，又要有有效长度：

#define MAXSIZE 50
typedef struct {
    int data[MAXSIZE];
    int length;
} SqList;

逐句读：MAXSIZE 是常量名字，这里代指 50；结构体内部有 50 个整数格子 data，还有一个整数 length；最后把这个类型起名为 SqList。它不是给某个具体表起名。

SqList L 表示 L 本身就是这一包东西，取字段写 L.length。SqList *p 表示 p 记住某个表的位置，沿 p 取字段写 p->length，等价于 (*p).length。

因此 insertOrdered(SqList *L,...) 中的 L 虽然也叫 L，却是指针，用 L->length；findInsertPos(SqList L,...) 中 L 是结构体值，用 L.length。变量名字一样，不意味着类型一样。

8. 链表：p 前进与改 p 的箭头不是一回事¶

结点可画为“数据格＋下一结点地址格”：

头结点 H ─→ [10 | next] ─→ [20 | next] ─→ [30 | NULL]

头结点是一个固定入口，数据域通常不参与题目。表长为 3，不是 4。指向 H 的 L，其 L->next 指向数据为 10 的结点。

代码	修改了什么	不要误解为
`p = p->next`	p 这个指针改指下一个结点	把链表的结点搬走
`p->next = q`	p 所指结点的 next 字段改指 q	仅让 p 前进一步
`p->data = 5`	p 所指结点的数据改为 5	交换了两个结点位置
`p == q`	问两个指针是否指向同一个结点	仅比较两个 data 是否相同

对 H→A→B→C，若 p 指 A，执行 p=p->next 后 p 指 B，但链仍原样。若执行 p->next=p->next->next，则链从 A 直接连 C，B 被跳过，p 仍指 A。

删除 B 前先把 B 的后继保留下来，再 free(B) 释放结点空间。free 不是自动帮你接好前后箭头；接箭头和还空间是两步。

malloc(sizeof(LNode)) 是申请一个结点大小的空间；它不会自动清空 next，必须初始化。calloc(n,sizeof(int)) 申请 n 个整数并将这些整数清零。申请可能失败返回 NULL，代码中的失败分支不是算法正常答案。

9. 树与递归：把“谁在等谁”画出来¶

根是最上面的起点，孩子是下一层相连结点；没有孩子的叫叶子。二叉树每个结点最多有左、右两个孩子，空孩子用 NULL 表示。

    A
   / \
  B   C

先序是“自己、左边、右边”，得到 A B C；中序是“左边、自己、右边”，得到 B A C；后序是“左边、右边、自己”，得到 B C A。这里的“左边”不是只看左孩子一次，而是把整棵左子树按同样规则处理完。

用“数结点”理解递归：

int countNodes(BiTree root) {
    if (root == NULL) return 0;
    int left = countNodes(root->lchild);
    int right = countNodes(root->rchild);
    return left + right + 1;
}

从 A 调用：A 先暂停，等 B 那次调用返回；B 又分别问两个空孩子，各收到 0，所以 B 返回 1。回到 A，A 的 left 现在是 1；A 再问 C，C 同样返回 1；最后 A 算 1+1+1=3。

每次调用都有自己的 root、left、right，B 的 left 不会覆盖 A 的 left。调用栈就是保存这些“还没做完、正在等孩子结果”的任务。沿一条很深的链递归，会同时挂起很多层，所以栈空间跟高度有关。

写递归先回答三问：空的时候返回什么；本次调用承诺计算什么；怎么利用孩子已经返回的结果。比如求高度的父节点取左右高度最大值加 1；WPL 则累加叶子贡献，不是一律“加 1”。

10. 队列和栈：后面图、树代码都要用¶

队列像排队，先来先处理。front 是下一个要取的位置，rear 是下一个可写的位置，待处理区间为 [front,rear)。

入队 queue[rear++]=A：先把 A 写入 rear 格，再 rear 加 1。出队 v=queue[front++]：先取 front 格，再 front 加 1。front==rear 时没人在排队。原数组里的旧值可能还在，但已不属于待处理区。

栈像叠盘子，后放的先取。top=-1 表示空栈；stack[++top]=A 先令 top=0 再放 A；v=stack[top--] 先取栈顶再下降。top 为 0 时有 1 个元素，top 为 1 时有 2 个，不是只有 1 个。

11. 图：顶点、边、矩阵、邻接表、visited¶

图可以表示地点与道路。地点叫顶点，相连关系叫边；有向边 A→B 允许从 A 到 B，不自动允许反向。入度是指向自己的边数，出度是自己发出的边数。

将 A、B、C 编号为 0、1、2。邻接矩阵 edge[i][j] 的行 i 是出发点、列 j 是到达点：

有向边 A→B、A→C、C→B	到 B	到 C
从 A 出发	1	1
从 B 出发	0	0
从 C 出发	1	0

邻接表则逐点列出出边：A:[B,C]，B:[]，C:[B]。G.adjList[v].firstarc 找到 v 的第一条出边；边结点 p->adjvex 存目的顶点编号；p=p->nextarc 是查看同一个 v 的下一条出边，不是沿图走到下一个顶点。

visited[w] 是编号 w 的地点是否已经发现。它是防止重复探索的笔记，不是道路本身。BFS 把发现但还没处理的点放队列，按距离层层展开；DFS 先深入一支，走不下去再返回。

Floyd 题的矩阵不同：存边权，无边用 INF，对角 0。其他无权题的“0 无边”不能无脑复制到 Floyd，否则无边会被误当成免费道路。

12. 时间和空间复杂度，先会数工作再写 O¶

O(n) 不是 n 秒，而是输入规模变大时，工作量按线性量级增长。看 100 个数大约 100 次、看 1,000 个数大约 1,000 次，属于这种情况。

两个先后进行的 n 次扫描，一共约 2n，仍记 O(n)；一层循环 n 次、里面每次再做 n 次，是 n²，记 O(n²)。循环套循环不必然平方：如果里面的指针总共只前进 n 次，总量仍可能线性。

二分每轮砍一半，长度 16→8→4→2→1，大约 4 次；长度 1,024 也只需约 10 次折半，这类记 O(log n)。

空间看额外同时占用多少。三个整数变量不随 n 增长，记 O(1)；新建 n 格数组记 O(n)；递归一次只往下一支深入，但上面仍有 h 层等待，所以要算 O(h) 栈空间。输出数组是否计入，要在答案里说明，不能一处计入、一处偷偷排除。

13. 如何实际运行一段最小 C 程序¶

本书题目通常给的是函数，不含 main，不能只复制一个函数就当作完整可执行程序。下例是完整入门示例，展示数组、循环、打印；不用修改任何正式教材文件：

#include <stdio.h>

int main(void) {
    int A[] = {6, 2, 5};
    int smallest = A[0];
    for (int i = 1; i < 3; i++) {
        if (A[i] < smallest) smallest = A[i];
    }
    printf("%d\n", smallest);
    return 0;
}

#include 告诉编译器我们要用标准打印函数；main 是程序入口；%d 代表以整数形式打印；\n 是换行；main 的 return 0 通常表示程序正常结束，不是说最小值是 0。结果在上一个 printf 中已经输出为 2。

在 macOS 上，若已安装命令行开发工具，把上面代码另存为学习用 demo.c，可运行 clang demo.c -o demo，再运行 ./demo。不熟悉终端也不影响先做纸上推演。

14. 开始读题之前的五个自检¶

数组长度 4，末元素下标是多少？答：3。
k=1 时执行 A[k++]=9，改哪个位置、之后 k 多大？答：改 A[1]，之后 k=2。
p 指 A，p=p->next 会修改 A 的 next 字段吗？答：不会，只改 p 自己。
top=0 时栈里有多少候选？答：1 个。
一棵根连两个叶子的树，按“结点层数”高度是多少，叶子到根有几条边？答：高度 2，边数 1。WPL 用后者。

能回答后开始第 1 题。遇到陌生符号就回来查，不需要靠猜。每道题先做手算表，再看完整函数和逐句说明，最后做自己的练习，暂时把复杂度和优化放到第二遍。

来源与边界¶

本课是为 Code59 新增的教学铺垫，不是原 PDF 的逐字内容。数据结构名称对应锁定正式稿的默认结构：顺序表回源 · PDF 第 4 页 · b_4_0；PDF 第 4 页 · b_4_3 ，链表回源 · PDF 第 10 页 · b_10_0；PDF 第 10 页 · b_10_2 ，树回源 · PDF 第 15 页 · b_15_0；PDF 第 15 页 · b_15_4 ，图回源 · PDF 第 20 页 · b_20_1；PDF 第 20 页 · b_20_6 。来源：Code59 正式稿。具体算法以各题题设、考试口径和校订说明为准。