写在前面

• 学会提问，用好 AI

第一站　Linux 的基础使用

• 终端与 Shell，文件系统与路径
• 操作文件，常用命令
• 重定向与管道

第二站　C++ 编程基础

• 编译运行，变量、条件、循环、函数
• 类与对象，继承与多态
• 多文件、库与 CMake

第三站　数据结构与算法

• 存下来：数组、vector、二维数组
• 算得快：复杂度，排序与二分，前缀和
• 建模：图，网格就是图
• 探索：栈与 DFS，队列与 BFS，树
• 最短路：递推，Dijkstra，A*，算法赛跑
• 回头看：标准库容器

回顾：小车走过的路

讲义里的标记：试一下、想一想、本节要点；标题带“选读”的第一遍可以跳过。
考核围绕讲义的正文和“试一下”出题。

一个好问题包含

把问题写清楚的过程，常常就把问题解决了。向人提问、向 AI 提问是同一项能力。

AI 可以帮你

• 解释刚接触的概念，用更基础的例子说明
• 检查你对报错、对知识的理解有没有漏洞
• 整理笔记和复盘

Linux 区分大小写：hello.txt ≠ Hello.txt

$ ls > list.txt          # 屏幕上什么也没有
$ echo "第二行" >> list.txt
$ printf '5\n12\n3\n8\n' > nums.txt
$ sort < nums.txt
12
3
5
8
$ sort -n < nums.txt > sorted.txt
$ ls nothing 2> err.txt

不加 -n：按文字排，"12" 在 "3" 前面
加 -n：按数值排，3、5、8、12

前一个命令的输出，直接作为后一个命令的输入，不需要中间文件。

每个命令只做好一件小事，用管道组合起来完成复杂任务。

$ g++ -std=c++17 hello.cpp -o hello
$ ls
hello  hello.cpp
$ ./hello
小车准备出发

改了源代码，要重新编译。hello.cpp 是源代码，hello 是可执行文件。

hello.cpp:4:34: error: expected ‘;’ before ‘return’

int main() {
    ⟦int p = 0;⟧    // 位置，初值 0
    p = p + 1;     // 前进一格
    p = p + 1;
    p = p + 1;
    std::cout << "位置：" << p << '\n';
}

int 是类型：p 保存整数。　简写：p += 1;　++p;

p ← p + 1

int p = 3;                 // 整数
double speed = 0.5;        // 小数
bool arrived = false;      // 真 / 假
char mark = 'S';           // 单个字符
std::string name = "小车"; // 字符串
const int END = 10;        // 常量，不能再改

std::string 需要 #include <string>

类型规定一个值能怎样用：3 能做加法，"3" 只是一段文字。

函数里单写 int p; 不保证是 0，
使用前先赋值。

每轮开始前检查条件：真就再执行一遍，假就结束。

输入 3：输出 1、2、3、到达目标
输入 0：循环体一次也不执行

⟦int⟧ remaining(⟦int position, int target⟧) {
    ⟦return⟧ target - position;
}

int main() {
    int d = remaining(5, 10);   // d = 5
    std::cout << "还差 " << d << " 格\n";
}

按值传递：交给函数的只是 p 的值。函数里的 p 是另一个变量，改它不影响 main 里的 p。

作用域：花括号里定义的变量，只在这对花括号里有效。

车一多，p1、p2、p3 满天飞……
能不能让每辆车自己记住位置，自己会移动？

Car carA;
Car carB;
carA.move(3);
carB.move(5);
carA.report();   // 3
carB.report();   // 5

$ echo 3 > in.txt
$ ./car < in.txt > out.txt
$ printf '1\n2\n3\n到达目标\n' > ans.txt
$ diff out.txt ans.txt
$ echo $?
0

$ diff out.txt ans2.txt     # ans2 第 3 行写成了 4
3c3
< 3
---
> 4

std::cin 读标准输入，std::cout 写标准输出：程序不用改。也可以 echo 3 | ./car。

diff 没有输出 = 完全相同。$? 是上一条命令的退出码，0 表示成功；return 0; 交出的就是它。

准备输入 → 运行 → 和期望输出比较：这就是测试。考核题的评测工具做的也是这件事。

void drive(⟦Car& car⟧, int target) {
    while (car.position < target) {
        car.step();
        car.report();
    }
}

Car a;
FastCar b;
drive(a, 3);
drive(b, 3);

普通车 在 1
普通车 在 2
普通车 在 3
快车 在 2
快车 在 4

Car& 是引用：不是副本，就是调用处那辆车本身。
回想“改不了外面的 p”：写成 int& p 就能改了。

#include "car.h"
#include <fmt/format.h>

void Car::report() {
    fmt::print("当前位置：{} 格\n", position);
}

$ g++ -std=c++17 main.cpp car.cpp -o car
⟦undefined reference to `fmt::v8::vprint(...)'⟧
$ g++ -std=c++17 main.cpp car.cpp -o car ⟦-lfmt⟧

同样是 undefined reference，这次缺的是 fmt 的实现。

-I目录 头文件去哪找　-L目录 库去哪找　-l库名 用哪个库

# CMakeLists.txt
cmake_minimum_required(VERSION 3.16)
project(CarDemo LANGUAGES CXX)

find_package(fmt REQUIRED)

add_executable(car main.cpp car.cpp)
target_compile_features(car PRIVATE cxx_std_17)
target_link_libraries(car PRIVATE fmt::fmt)

“要做出一个叫 car 的程序，由这两个文件构建，用 C++17，链接 fmt。”

$ cmake -S . -B build  # 读配置，生成构建文件
$ cmake --build build  # 真正编译、链接
$ ./build/car

再构建一次：

$ cmake --build build
[100%] Built target car

没有改动就不重新编译；改了 car.cpp，只重新编译它。

下标从 0 开始：5 个元素是 0～4。

• 嵌套相乘：内层 n−1、n−2、…、0 次，共 n(n−1)/2 → O(n²)
• 先后执行取最大：O(n) 读入 + O(n²) 比较 → O(n²)
• 看最坏情况：猜数字运气好一次就中，但要保证“最多几次”
• 空间复杂度：内存随规模怎样增长。n 个数的数组 O(n)

二分能排除一半，是因为数据有序。乱序的数据呢？ → 先排序。

int t[5] = {32, 17, 45, 23, 8};
std::sort(t, t + 5);
// 8 17 23 32 45

t 到 t + 5：包含开头，不含结尾。O(n log n)。
平时用 std::sort；学冒泡、快排是为了理解思路。

快速排序（选读）：选基准、分两边、递归。递归一定要有终止条件。

int lo = 0, hi = n - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == x) return mid;
    if (a[mid] < x) lo = mid + 1;  // 太小了
    else hi = mid - 1;             // 太大了
}
return -1;

h 不必是某个固定公式，但要满足：

1. 好算：不能为了估计再搜一遍
2. 不高估：h ≤ 真实剩余代价 → 仍保证最短
3. 每走一步，h 减少不超过这一步的代价，终点 h = 0
   格子取出后不再处理时需要；满足它，2 也成立

std::map<std::string, int> pos;  // 名字 → 位置
pos["小车一号"] = 3;
pos["小车二号"] = 5;
pos["小车一号"] += 2;            // 变成 5
pos.count("小车三号");           // 0：没有

for (auto item : pos) {          // 按名字顺序
    std::cout << item.first << ": "
              << item.second << '\n';
}

注意：pos[不存在的键] 会自动插入。只想判断有没有，用 count。