速成 · 程序设计基础 | L.D.J 的私家工坊

这门课不是在背语法，而是在练一条完整链路：把题意翻译成数据和步骤，再把步骤翻译成能被机器严格执行的程序。源目录保留的正式课件从第二讲开始，因此这里也从第二讲讲起，不补造缺失的第一讲内容。

1. 一张图看完整门课

题目
  ↓  明确输入、输出、约束
数据表示：类型、范围、精度、数组、字符串
  ↓
流程组织：顺序、选择、循环
  ↓
模块拆分：函数、参数、返回值、递归
  ↓
内存访问：地址、指针、动态空间
  ↓
算法选择：枚举、排序、查找、搜索……
  ↓
测试：正常值、边界值、异常输入

遇到新题，先顺着这张图往下走。不要一看到题面就敲代码。

2. 先把题读成四句话

动手前写清楚：

输入有几组？每组有哪些量？以什么结束？
输出什么？格式、精度、换行是否固定？
数据最大多大？int 会不会溢出？数组开多大？
从输入到输出，数学上要经过哪些步骤？

例如“连续读入两个整数，输出它们的和，直到文件结束”，核心不是加法，而是输入循环：

int a, b;
while (scanf("%d%d", &a, &b) == 2) {
    printf("%d\n", a + b);
}

scanf 的返回值是成功读到的数据项数。这里写 == 2 比只判断 != EOF 更严谨：输入格式错误时也能停下来。

3. 类型决定“这一串比特怎样解释”

常见类型可以先这样记：

类型	常见用途	常见风险
`char`	字符、短整数	字符 `'0'` 不是整数 `0`
`int`	一般整数	乘法、阶乘很容易溢出
`long long`	较大整数	仍然有范围上限
`float`	单精度小数	有效数字少
`double`	常用浮点数	大多数小数不能精确表示

三个高频结论：

整数除法会截去小数：5 / 2 == 2，而 5.0 / 2 == 2.5；
浮点数通常不要直接用 == 比较，可判断 fabs(a - b) < eps；
计算过程也会溢出，哪怕最终结果能放下。写 1LL * a * b 可先把乘法提升为 long long。

4. 控制结构：程序只有三种基本走法

顺序：从上到下执行；
选择：if、if/else、switch；
循环：while、for、do/while。

选择结构先写“互斥条件”，循环结构先写三个东西：

循环前：状态如何初始化？
循环中：满足什么条件继续？
每一轮：什么量发生变化，为什么一定会结束？

若这三个问题答不出来，代码通常会死循环、漏算或多算一次。

循环边界的最常见错误

长度为 n 的数组合法下标是 0 到 n - 1：

for (int i = 0; i < n; ++i) {
    /* 使用 a[i] */
}

把 < n 写成 <= n 就会越界。越界不保证立刻崩溃，它可能悄悄改坏旁边的数据，因此尤其难查。

5. 函数：先设计接口，再写内部过程

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

读函数时只问三件事：输入是什么、输出是什么、是否修改外部数据。C 的普通参数是值传递，函数拿到的是副本：

void bad_swap(int a, int b);        /* 改不了调用者的变量 */
void swap(int *a, int *b);          /* 通过地址修改调用者 */

递归函数还必须有：

基本情况：什么时候直接得到答案；
规模缩小：递归调用的问题必须更小；
回溯组合：子问题答案怎样拼成原问题答案。

缺少前两项会无限递归，直到栈溢出。

6. 数组与字符串：连续空间加边界

数组是一段连续的同类型空间。字符串则是以 \0 结束的字符数组：

char s[6] = "hello";  /* 5 个可见字符 + 1 个 '\0' */

必须同时记住“容量”和“当前有效长度”。strlen(s) 不统计结尾的 \0，而 sizeof(s) 在 s 仍是数组时给出整个数组所占字节数。

读一整行优先用有容量限制的 fgets：

char line[1024];
if (fgets(line, sizeof line, stdin) != NULL) {
    /* line 可能保留末尾换行符 */
}

课件介绍了历史函数 gets，但它无法知道目标数组容量，现代 C 已将其移除，不应再使用。

7. 指针：地址不是数据本身

int value = 18;
int *p = &value;
*p = 20;

p 保存地址，*p 才是该地址处的 int。类型告诉编译器：解引用时读多少字节、p + 1 应跨过多少字节。

指针的安全底线：

定义后立即指向合法对象，暂时没有目标就设为 NULL；
不解引用 NULL、未初始化指针或已经 free 的空间；
指针运算只在同一个数组及其末尾后一位置范围内进行；
malloc 后检查返回值，不再使用时 free，并避免重复释放。

8. 排序、查找与复杂度

数组问题先问“是否需要有序”。

线性查找：无序也能用，最坏检查 $n$ 个元素；
二分查找：要求查找区间具有单调性，每轮砍掉一半；
冒泡排序：便于理解交换和稳定性，但时间复杂度是 $O(n^2)$ ；
qsort：通过函数指针传入比较规则，可处理多种类型。

二分不是只用来“在数组里找某个数”。只要答案满足“左边都可行、右边都不可行”之类的单调性，就可以二分答案。

9. 一套考场调试路线

编译错误

从编译器报告的第一处错误开始：检查括号、分号、变量声明、函数原型、格式字符串和类型。后续几十条错误可能只是第一处错误引发的连锁反应。

运行崩溃

优先检查：

数组下标；
指针是否初始化；
递归是否收敛；
除数是否为零；
scanf 是否少写了 &。

答案错误

准备最小反例，手算每一步，然后打印中间状态：

fprintf(stderr, "i=%d sum=%lld\n", i, sum);

重点测：最小输入、最大输入、空或单元素、全部相等、已经有序、逆序、正负零、重复值和刚好卡在边界上的值。

超时或超内存

先估数量级。 $n=10^5$ 时，两层完整循环约有 $10^{10}$ 次操作，通常不可接受；此时应找排序、二分、哈希或更好的数学关系，而不是继续微调常数。

10. 最后检查清单

输入格式与返回值判断正确；
类型和格式符匹配；
中间计算不会溢出；
循环一定结束且没有少一、多一；
数组和字符串不越界；
浮点比较使用合理误差；
函数接口表达清楚，递归有基本情况；
动态内存成对申请、释放；
输出空格、换行和小数位完全符合要求。

能稳定走完这份清单，就已经掌握了这门课真正有用的部分。

速成 · 程序设计基础