Mdr-C-Tutorial

主题

在开始数据结构与算法之前 ​

从本章开始，我们将开始学习数据结构与算法。

如果你单纯想学数据结构与算法，或者在为一门名叫数据结构与算法的课程的期末考试做准备，推荐学习 Hello 算法。这是笔者到目前为止见过的最优质的中文数据结构与算法教程，我每个暑假都会把它安利给计算机专业的大一新生。

如果你想考 408（这里面有 45 分的数据结构），请看相应的参考书。（没有哪个考研的会来这吧）

MCT 的数据结构与算法模块着重讲解各个数据结构与算法的原理解析和形式化证明，以及它们的 C 语言实现，略微涉及它们在实际工程中的应用。

1. 这门课到底在训练什么 ​

很多同学会把“会做题”和“会算法”画等号，但这两个目标并不完全一致。会做题往往意味着你能在熟悉题型下迅速套用方法；而会算法更强调把问题抽象成可验证的状态对象、关系对象和约束对象，然后把解法稳定地落到代码中。本模块更偏后者：你会看到定义、证明、复杂度和实现被放在同一条主线上，它的目标是让你在面对陌生问题时也能从零建立解法，而不是只记住若干模板。

2. 建议的学习顺序 ​

建议先把“概念层”学扎实，再进入“实现层”。具体可以按这条线走：先读清楚抽象数据类型与线性结构，再进入递归式、复杂度和分治分析，最后再系统刷动态规划、图与贪心等主题。这样安排的原因很简单：如果前面的表示与分析语言不稳定，后面的高阶算法会变成“背结果”；而一旦前面的语义统一了，后面每个专题都会自然连起来。

3. 用 C 写算法时的最小工作流 ​

在 C 语言里，算法代码能否长期可用，很大程度取决于测试入口是否清晰。建议从第一章开始就固定一套最小工作流：准备确定输入、打印关键中间结果、最后给出结果值。下面这段代码演示了一个最小可复用入口，它不依赖复杂框架，但足够支撑大多数算法章节的验证过程。

c
#include <stdio.h>

static int sum_array(const int *a, int n) {
    int s = 0;
    for (int i = 0; i < n; ++i) {
        s += a[i];
    }
    return s;
}

int main(void) {
    int a[] = {3, 1, 4, 1, 5};
    int n = (int)(sizeof(a) / sizeof(a[0]));
    printf("sum = %d\n", sum_array(a, n));
    return 0;
}

可能的输出（示例）：

bash

sum = 14

4. 我可以去哪刷题？ ​

  1. Codewars：标签选择 Algorithms 和 Data Structures。 tags
  2. NOI OpenJudge：这里提供了一些常见数据结构与算法的经典题。
  3. 洛谷：它虽然主要面向信息学奥赛生，但对于所有数据结构与算法的学习者来说都是全面的题库，其中题目的难度和广度跨越都很大。