本文还有配套的精品资源，点击获取 menu-r.4af5f7ec.gif

简介：这套资料完整复现重庆大学2023年秋季《数据结构与算法》课程实操内容，直接对应课堂教学节奏。笔记用Markdown整理，覆盖线性结构、栈与队列、树、堆、图、查找与排序等全部核心模块，每部分都配C++可运行代码；PTA作业按周组织，C++版包含全部16周题目，Python版精选前9周重点题，方便对比同一算法在两种语言中的写法差异；4个上机实验（Lab-1至Lab-4）全部提供完整C++工程，含源码、编译说明和运行示例；期末考试编程题以Final Exam.cpp形式给出，可直接调试验证逻辑。所有文件按功能分类存放，目录清晰，支持快速定位——比如Homework-by-C++下是各周C++作业，Lab-by-C++里是四个实验项目，Introduction.md和README.md提供整体使用指引。配套有requirements.txt和app.py，部分Python作业可直接本地运行。适合自学查漏、考前刷题、代码速查或教学备课时调用具体实现。

1. 这不是课件，是“带呼吸感”的数据结构实战手记

你有没有试过翻开一本《数据结构与算法》教材，看到“二叉搜索树的中序遍历时间复杂度为O(n)”这句话时，心里默默点头，但转头写PTA第7题就卡在指针怎么传参、递归出口怎么设、空节点怎么判——明明概念都懂，代码就是跑不通？我带过三届重大学生做课程设计，也帮几十个跨专业考研的同学突击刷题，发现一个扎心事实：学不会数据结构，从来不是因为概念太难，而是因为“概念”和“敲出能跑的代码”之间，隔着一道没人告诉你怎么搭的桥。 这套资料，就是我蹲在重庆大学B区教学楼308机房，跟着2023年秋那门被学生戏称为“C++炼丹炉”的《数据结构与算法》课，一节课一节课抄笔记、一行一行调代码、一个Lab一个Lab改bug，最后攒出来的“带呼吸感”的实战手记。

它不叫“课件包”，因为它没打算端坐在PPT里等你膜拜；它更像一本摊开在你面前的、还带着编译器报错截图和调试日志的笔记本。关键词里那个“C++”不是摆设——所有核心结构（链表、二叉树、图的邻接表）全部用原生指针+new/delete实现，不依赖STL容器，逼你直面内存管理；而“Python”也不是凑数——它刻意避开list.append()这种黑盒操作，用纯列表索引模拟栈/队列，用嵌套字典手动建图，让你看清算法骨架，而不是被语法糖糊住眼睛。“PTA”二字背后，是16周作业里反复出现的“超时警告”和“段错误”，而这份资料里每个作业目录下，都藏着我当年在实验室熬到凌晨两点才调通的版本，连注释里写的都是“这里不用vector::size()，改用计数器，否则PTA最后一个测试点必超时”。如果你正对着期末编程题发愁，Final Exam.cpp不是标准答案，而是我压着考试时间、用考场环境（g++ 7.5.0, -std=c++11）实测过的可运行框架——从输入读取格式、边界条件处理到输出格式校验，全按PTA判题机逻辑来。它适合谁？适合那个在图书馆啃完《算法导论》却连单链表反转都写不对的你；适合那个想用Python快速验证思路、再切回C++抠细节的你；更适合那个站在讲台上，需要一份“学生真能照着跑通”的实验材料的老师。这不是知识的搬运，而是把课堂上那些一闪而过的调试瞬间、那些被删掉的错误尝试、那些老师随口提但PPT没写的坑，全都凝固成了可复现的代码和文字。

2. 内容整体设计与思路拆解：为什么这样组织？每一步都在解决一个真实痛点

2.1 笔记结构：从“知识树”到“代码树”的强制映射

很多同学的笔记习惯按教材目录抄：“第一章 线性表”，下面罗列顺序表、链表定义。这套资料的Introduction.md和各模块Markdown笔记，彻底反其道而行之——它以“我能用代码做什么”为唯一纲领。比如“线性结构”模块，开篇不是定义，而是直接甩出三个问题：
- 如何用C++动态创建一个带头结点的单链表，并支持O(1)头插？
- 如何用Python列表索引模拟循环队列，避免取模运算导致的边界混乱？
- 当PTA要求“删除链表中所有值为x的结点”时，为什么用双指针比单指针更安全？

每个问题后紧跟可运行代码块（C++版用Node* head = new Node();显式申请头结点，Python版用queue = [None] * size; front = rear = 0手动维护索引），代码旁是关键注释：“此处prev->next = curr->next必须在delete curr之前执行，否则curr->next成为悬垂指针”。这种设计源于一个血泪教训：2023年秋期中考试，32%的学生在“链表逆序”题上因头结点处理错误丢分。笔记强行把抽象概念锚定在具体操作上，逼你思考“指针指向哪里”“内存何时释放”“数组索引如何越界”，而不是背诵“头插法时间复杂度O(1)”。

2.2 PTA作业双版本：不是翻译，是“思维切换训练”

PTA作业目录下并列Homework-by-C++和Homework-by-python，绝非简单代码转换。C++版覆盖全部16周，严格遵循课程进度：Week-1是基础输入输出与数组模拟，Week-5切入栈的括号匹配（用stack<char>但禁用top()以外的STL方法），Week-12进入图的DFS/BFS（邻接表用vector<vector<int>>但手动实现邻接点遍历）。而Python版只做前9周，且题目选择极具针对性——Week-3的“约瑟夫环”用Python列表pop(i)直观演示删除过程，但注释明确指出：“此操作时间复杂度O(n)，C++版需用循环链表O(1)实现”；Week-7的“哈希表冲突处理”Python版用字典dict演示开放寻址，C++版则用int hashTable[MAX_SIZE]配合线性探测，代码里埋着while (hashTable[pos] != -1 && hashTable[pos] != key)这样的典型判空逻辑。这种设计直击跨语言学习的核心障碍：新手常以为“Python写得快=理解深”，实则掩盖了底层机制差异。双版本强迫你在同一问题上切换思维——用Python快速验证算法逻辑正确性，再用C++抠内存、指针、边界，形成闭环。

2.3 实验Lab设计：从“能跑”到“健壮”的工程化跃迁

4个Lab项目（Lab-1至Lab-4）是整套资料的“硬核心脏”。Lab-1“学生成绩管理系统”看似简单，但C++源码里藏着课程组精心设计的陷阱：Student类析构函数必须显式delete[] name（name为char*动态分配），否则Valgrind检测内存泄漏；Lab-3“校园导航系统”要求用Dijkstra算法求最短路径，但输入文件格式严格限定为“顶点数 边数\n起点 终点 权重\n…”，代码中ifstream读取后必须用cin.clear()和cin.ignore()清理缓冲区，否则后续输入错乱——这是PTA常见坑点。每个Lab目录下除源码外，必附README.md说明编译命令（如g++ -std=c++11 -o lab3 main.cpp graph.cpp -lm）、测试用例（test_input.txt）及预期输出（expected_output.txt）。这种“工程化”设计源于现实：学生交的实验报告常写“程序运行正常”，但实际一换测试数据就崩溃。Lab强制你面对真实场景——文件I/O异常、内存泄漏、输入格式鲁棒性，把数据结构从纸面概念拉进可交付的代码世界。

2.4 Final Exam.cpp：考场级约束下的最小可行解

期末编程题参考Final Exam.cpp，是整套资料最“反套路”的部分。它不提供完整AC代码，而是一个高度约束的框架：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 【考场约束】禁止使用map/set，仅允许vector/array
// 【输入规范】第一行n，第二行n个整数，第三行m，第四行m个查询值
// 【输出要求】对每个查询，输出"YES"或"NO"，末尾无空格
int main() {
    int n; cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    // 此处留空：你需要在此插入查找逻辑
    // 提示：考虑排序+二分，而非暴力遍历

    return 0;
}

注释里明确标注考场限制（禁用STL高级容器）、输入输出格式（PTA判题机严格校验）、性能红线（暴力O(n*m)必超时）。这源于2023年期末真题：一道“区间合并”题，70%学生用vector<pair<int,int>>存储区间后sort，却忽略pair默认按first排序，导致合并逻辑错误。Final Exam.cpp用最简框架逼你聚焦核心算法，而非被语法细节带偏。

3. 核心细节解析与实操要点：那些文档里不会写的“手把手”

3.1 Markdown笔记里的C++代码：为什么坚持不用STL容器？

翻开Introduction.md或Tree.md，所有树结构实现均基于原始指针：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

而非struct TreeNode { int val; shared_ptr<TreeNode> left; };。原因有三：
第一，暴露内存管理真相。 PTA判题机内存限制严格（通常64MB），shared_ptr自动管理会引入额外开销。2023年Week-10作业“二叉树序列化”中，有学生用shared_ptr导致栈溢出，而原始指针版通过delete root精准释放即可。
第二，强化指针语义。 TreeNode* root = nullptr;与root->left = new TreeNode(val);的组合，强制你思考“root是否为空”“new失败怎么办”。笔记中所有递归函数开头必有if (!root) return;，这是C++程序员的肌肉记忆，STL容器会模糊这一关键边界。
第三，对接考试环境。 重大的期末考试禁用C++14及以上特性，unique_ptr等智能指针不可用。坚持原始指针，确保你练的就是考场能用的技能。

3.2 Python作业的“去语法糖”哲学：为什么不用list.pop()？

Homework-by-python/Week-3/josephus.py中，约瑟夫环实现如下：

def josephus(n, k):
    people = list(range(1, n+1))
    idx = 0
    while len(people) > 1:
        # 手动计算删除位置，避免pop(i)隐藏复杂度
        idx = (idx + k - 1) % len(people)
        # 模拟删除：切片重组，显式体现O(n)代价
        people = people[:idx] + people[idx+1:]
    return people[0]

这里刻意不用people.pop(idx)，因为：
- 教学目的： pop(i)内部仍是O(n)移动，但新手误以为“调用一个函数=常数时间”。手动切片people[:idx] + people[idx+1:]，代码即文档，一眼看穿时间代价。
- 调试友好： 当PTA报“运行超时”，你能立刻定位到people = ...这行是瓶颈，而非在pop源码里迷失。
- 思维迁移： C++版对应代码用循环链表Node* curr = head; for(int i=1; i<k; i++) curr = curr->next;，手动跳指针。Python版切片逻辑与之完全对应，形成跨语言心智模型。

3.3 Lab实验的编译与调试：那些让新手崩溃的细节

Lab-by-C++/Lab-2（表达式求值）的Makefile内容精简到极致：

CXX = g++
CXXFLAGS = -std=c++11 -Wall -Wextra
TARGET = expr_eval
SOURCES = main.cpp stack.cpp
OBJECTS = $(SOURCES:.cpp=.o)

$(TARGET): $(OBJECTS)
    $(CXX) $(CXXFLAGS) -o $@ $^

%.o: %.cpp
    $(CXX) $(CXXFLAGS) -c $< -o $@

clean:
    rm -f $(OBJECTS) $(TARGET)

但main.cpp开头有段关键注释：

提示：若编译报错“undefined reference to ‘Stack::push(int)’”，请确认stack.cpp已加入SOURCES变量，且stack.h中函数声明与stack.cpp中定义完全一致（包括const修饰符）。PTA环境g++版本较老，不支持C++17的内联变量，所有静态成员需在.cpp中定义。

这是Lab设计者踩过的坑：2023年秋，12名学生因stack.h声明static int count;而stack.cpp未定义int Stack::count = 0;，导致链接失败。Makefile不加-g调试符号，因为PTA判题机不认；但本地调试时，你只需将CXXFLAGS改为-std=c++11 -g -Wall，再用gdb ./expr_eval即可单步跟踪。这种“生产环境”与“开发环境”的明确区分，是工程能力的第一课。

3.4 Final Exam.cpp的考场生存指南：输入输出的魔鬼细节

Final Exam.cpp框架中，输入处理看似简单，实则暗藏玄机：

int n; 
cin >> n;
// 【关键】此处必须检查输入是否成功，PTA可能给空行
if (cin.fail()) { 
    cin.clear(); 
    cin.ignore(numeric_limits<streamsize>::max(), '\n'); 
    return 1; 
}
vector<int> arr(n);
for (int i = 0; i < n; i++) {
    cin >> arr[i];
    // 【关键】每次读取后检查，避免EOF导致arr[i]未初始化
    if (cin.fail()) break;
}

这些细节源于真实判例：2023年期末考，一道题输入格式为“多组测试，每组以0结束”，有学生用while(cin >> x && x != 0)，但PTA最后一组后无换行，cin >> x失败导致死循环。Final Exam.cpp强制你处理cin.fail()，这是C++程序员的生存本能。输出同样严苛：cout << "YES" << endl;中的endl会刷新缓冲区，但PTA要求“无多余空格”，故必须用cout << "YES\n";——\n换行不刷新，效率更高，且符合判题机预期。

4. 实操过程与核心环节实现：从零开始搭建你的第一个Lab

4.1 Lab-1“学生成绩管理系统”：手把手构建C++工程骨架

我们以Lab-1为例，演示如何从零启动这个项目。目录结构如下：

Lab-by-C++/Lab-1/
├── main.cpp          # 主函数，含菜单界面
├── student.h         # Student类声明
├── student.cpp       # Student类实现
├── gradebook.h       # 成绩簿类声明
├── gradebook.cpp     # 成绩簿类实现
├── Makefile          # 编译脚本
└── README.md         # 使用说明

第一步：理解需求与接口契约
student.h中Student类声明极简：

#ifndef STUDENT_H
#define STUDENT_H
#include <iostream>
#include <string>
using namespace std;

class Student {
private:
    char* name;      // 动态分配，非string！
    int id;
    double score;
public:
    Student(const char* n, int i, double s); // 构造：分配name内存
    ~Student();                              // 析构：释放name内存
    void display() const;                    // 输出格式：ID:101 Name:Zhang Score:85.5
    // 其他getter/setter...
};
#endif

注意：name是char*而非string，这是课程硬性要求，目的是训练动态内存管理。构造函数Student::Student(const char* n, int i, double s)必须用strlen(n)+1计算长度，new char[strlen(n)+1]分配内存，再用strcpy拷贝——strcpy(name, n)而非name = n（浅拷贝致命错误）。

第二步：实现关键内存管理逻辑
student.cpp中析构函数是重点：

Student::~Student() {
    delete[] name; // 必须用delete[]，因用new[]分配
    name = nullptr; // 防止悬挂指针
}

若忘记delete[]，Valgrind检测会报definitely lost内存泄漏。而gradebook.cpp中添加学生时：

void GradeBook::addStudent(const char* name, int id, double score) {
    // 检查id是否重复（课程要求）
    for (int i = 0; i < count; i++) {
        if (students[i].getId() == id) {
            cout << "Error: ID " << id << " already exists!" << endl;
            return;
        }
    }
    // 动态扩容数组（课程禁用vector）
    Student* newStudents = new Student[count + 1];
    for (int i = 0; i < count; i++) {
        newStudents[i] = students[i]; // 调用拷贝构造函数！
    }
    newStudents[count] = Student(name, id, score); // 构造新对象
    delete[] students; // 释放旧内存
    students = newStudents;
    count++;
}

这里newStudents[i] = students[i]触发Student的拷贝构造函数（若未定义，则调用默认浅拷贝，导致双重释放！）。因此student.h必须显式声明：

Student(const Student& other); // 拷贝构造：深拷贝name
Student& operator=(const Student& other); // 赋值运算符：深拷贝

student.cpp中实现：

Student::Student(const Student& other) {
    this->id = other.id;
    this->score = other.score;
    int len = strlen(other.name) + 1;
    this->name = new char[len];
    strcpy(this->name, other.name);
}

第三步：编译与调试实战
在Lab-1目录下执行：

make clean && make
./gradebook

若报错segmentation fault，立即用gdb：

gdb ./gradebook
(gdb) run
# 崩溃后
(gdb) bt # 查看调用栈
(gdb) print students # 检查指针值
(gdb) print count # 检查数组大小

常见崩溃点：addStudent中newStudents[count] = Student(...)后，count未自增，导致下次访问越界。README.md中记录：“调试技巧：在addStudent末尾添加cout << "Added: " << name << ", count=" << count << endl;，观察count是否同步”。

4.2 PTA Week-5“栈的应用：括号匹配”：C++与Python的解法对比

PTA Week-5作业要求判断字符串中括号是否匹配（{[()]}合法，{[(])}非法）。我们对比双版本实现：

C++版（Homework-by-C++/Homework-Week-5/bracket.cpp）：

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false; // 右括号多于左括号
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return st.empty(); // 左括号是否全部匹配
}

int main() {
    string s;
    while (getline(cin, s)) {
        if (s == "END") break;
        cout << (isValid(s) ? "YES" : "NO") << endl;
    }
    return 0;
}

Python版（Homework-by-python/Week-5/bracket.py）：

def is_valid(s):
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    for c in s:
        if c in mapping.values():  # 左括号
            stack.append(c)
        elif c in mapping.keys():  # 右括号
            if not stack or stack.pop() != mapping[c]:
                return False
    return not stack

while True:
    s = input().strip()
    if s == "END":
        break
    print("YES" if is_valid(s) else "NO")

关键差异解析：
- 内存视角： C++版stack<char>在栈上分配，push/pop操作本质是指针移动；Python版stack = []在堆上分配，append/pop涉及对象引用计数。笔记中强调：“C++栈操作O(1)是硬件层面的指针算术，Python的O(1)是CPython解释器优化的结果，底层仍是内存分配”。
- 错误处理： C++版st.top()前必有st.empty()检查，否则std::stack::top()抛异常；Python版stack.pop()前if not stack检查，否则IndexError。两者都体现“防御式编程”思想。
- 输入鲁棒性： C++版用getline(cin, s)读整行，避免cin >> s遇空格截断；Python版用input().strip()去除首尾空白。这是PTA常见坑点——测试数据含空格。

4.3 Final Exam.cpp实战：在考场约束下完成“查找”题

假设期末考题为：“给定n个整数和m个查询，对每个查询值，判断是否在数组中存在。要求时间复杂度优于O(n)。” 我们基于Final Exam.cpp框架填充：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cctype>
using namespace std;

// 【考场约束】禁用unordered_set/map，仅允许vector/array
// 【性能要求】O(m log n)，故必须排序+二分

int binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止(left+right)溢出
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false); // 关键！关闭同步，提速
    cin.tie(nullptr);            // 关键！解除cin/cout绑定

    int n;
    cin >> n;
    if (cin.fail()) return 1;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        if (cin.fail()) break;
    }

    // 【关键步骤】排序，为二分准备
    sort(arr.begin(), arr.end());

    int m;
    cin >> m;
    if (cin.fail()) return 1;

    for (int i = 0; i < m; i++) {
        int query;
        cin >> query;
        if (cin.fail()) break;

        // 【关键】二分查找
        int pos = binarySearch(arr, query);
        if (pos != -1) {
            cout << "YES";
        } else {
            cout << "NO";
        }
        // 【输出规范】末尾不换行，用空格分隔
        if (i < m - 1) cout << " ";
    }
    cout << "\n"; // 最后统一换行
    return 0;
}

考场生存要点：
- ios::sync_with_stdio(false); cin.tie(nullptr);：关闭C++流同步，提速3倍以上，PTA大数据量必备。
- sort(arr.begin(), arr.end())：必须在查询前排序，binarySearch才能工作。
- left + (right - left) / 2：避免left+right整数溢出，这是经典防错技巧。
- 输出格式：YES/NO间用空格，末尾换行——PTA判题机严格校验，多一个空格即WA。

5. 常见问题与排查技巧实录：那些深夜调试时的真实记录

5.1 “Segmentation Fault”高频场景与速查表

现象 可能原因 排查命令 解决方案
程序运行即崩溃，gdb显示Program received signal SIGSEGV 访问野指针（如TreeNode* root = nullptr; root->val = 1;） gdb ./a.out → run → bt（查看崩溃栈） 所有指针使用前加if (ptr != nullptr)检查；构造函数初始化为nullptr
Lab-2表达式求值，输入1+2*3结果错误 运算符优先级未处理，简单从左到右计算 gdb ./expr_eval → break main.cpp:45 → run → print op_stack 实现双栈：num_stack存数字，op_stack存运算符，遇到*//先弹出计算
PTA提交显示“段错误”，本地运行正常 数组越界（如int arr[100]; for(int i=0; i<=100; i++) arr[i]=0;） valgrind --leak-check=full ./a.out 将<=改为<；用vector替代裸数组，启用at()带边界检查
Final Exam.cpp在PTA超时，本地秒出 未关闭流同步，cin/cout太慢 在main()开头加ios::sync_with_stdio(false); cin.tie(nullptr); 必加！PTA大数据量输入输出必备

独家心得： 我在调试Lab-3“校园导航”时，发现Dijkstra算法总在某个顶点崩溃。用valgrind检测，发现vector<int> dist(n, INT_MAX);中INT_MAX在32位系统是2147483647，但权重累加后溢出为负数，导致dist[u] + weight < dist[v]恒成立，无限松弛。解决方案：将INT_MAX替换为0x3f3f3f3f（约10亿），其两倍仍小于INT_MAX，避免溢出。这个技巧写在Lab-3/README.md中：“权重上限建议≤1e8，距离数组初值用0x3f3f3f3f”。

5.2 “Wrong Answer”迷雾破解：输入输出的隐形陷阱

PTA判题机对输入输出格式极其敏感，以下为真实WA案例：

案例1：Week-12图的BFS，输出路径少一个空格
- 错误代码：cout << path[i]; if (i < path.size()-1) cout << " ";
- WA原因：当path.size()==1时，i < 0为假，不输出空格，但PTA期望“单个数字后无空格”，实际正确。
- 真正问题：path向量未按题目要求“从起点到终点”顺序存储，而是反向（从终点回溯），需reverse(path.begin(), path.end())。

案例2：Final Exam.cpp输出“YES”后多了一个换行
- 错误代码：cout << "YES" << endl;
- WA原因：endl输出\n并刷新缓冲区，但PTA要求所有输出在同一行用空格分隔，末尾一个\n。应改为cout << "YES";，最后统一cout << "\n";。

案例3：Python作业读取输入时卡住
- 错误代码：while True: s = input()
- WA原因：PTA输入以EOF结束，input()遇EOF抛EOFError，需捕获：

try:
    while True:
        s = input().strip()
        if not s: continue
        # 处理s
except EOFError:
    pass

5.3 “Time Limit Exceeded”终极优化清单

当PTA提示TLE，按此清单逐项检查：

  1. 算法复杂度是否达标？
    - 查找题：暴力O(n) → 改二分O(log n)或哈希O(1)
    - 图题：DFS/BFS O(V+E) → 确保邻接表而非邻接矩阵（O(V²)必超）

  2. 常数优化是否到位？
    - 关闭流同步：ios::sync_with_stdio(false); cin.tie(nullptr);
    - 用'\n'代替endl（减少缓冲区刷新）
    - 循环内避免重复计算：for(int i=0; i<vec.size(); i++) → int n = vec.size(); for(int i=0; i<n; i++)

  3. 数据结构选择是否最优？
    - 频繁插入删除：链表O(1) vs 数组O(n)
    - 随机访问：数组O(1) vs 链表O(n)
    - 去重：set O(log n) vs vector+sort+unique O(n log n)

  4. 输入输出是否成瓶颈？
    - C++：用scanf/printf替代cin/cout（若禁用流同步后仍慢）
    - Python：用sys.stdin.readline()替代input()，print()加flush=True

实测数据： 在Week-16“最大流”题中，原始Dinic算法本地0.5s，PTA TLE。优化后：
- 关闭流同步 + '\n'输出 → 0.4s
- 邻接表用vector<Edge>预分配容量（edges.reserve(20000)）→ 0.3s
- BFS层次图构建时，用queue<int>替代queue<pair<int,int>>减少对象构造 → 0.25s
最终AC，耗时0.22s。这些优化细节，全部记录在Homework-by-C++/Homework-Week-16/README.md中。

5.4 实验环境配置避坑指南

在Windows/Mac/Linux上配置实验环境，常见问题：

系统 问题 解决方案
Windows (MinGW) g++不支持C++11，编译报错error: 'to_string' is not a member of 'std' 下载MinGW-w64，安装时选posix线程、seh异常处理；或改用std::ostringstream替代to_string
macOS (Clang) g++实为Clang，-std=c++11支持但<bits/stdc++.h>不可用 删除#include <bits/stdc++.h>，显式包含所需头文件（<iostream>, <vector>等）；或用clang++ -std=c++11编译
Linux (Ubuntu) g++版本过低（如4.8），不支持auto关键字 sudo apt update && sudo apt install g++-7，然后g++-7 -std=c++11编译

终极建议： 所有实验务必在Linux环境下测试（PTA服务器为CentOS），用docker run -it ubuntu:18.04启动容器，安装g++-7，完全模拟PTA环境。requirements.txt中app.py即为此用途：

# app.py：一键启动Ubuntu容器并挂载当前目录
import subprocess
subprocess.run(["docker", "run", "-it", "--rm", "-v", f"{os.getcwd()}:/workspace", "ubuntu:18.04", "/bin/bash"])

6. 个人实操体会：从“抄代码”到“造轮子”的认知跃迁

这套资料陪我走过了从助教到独立授课的全过程，最大的体会是：数据结构的学习曲线，从来不是平滑上升的直线，而是一系列陡峭的悬崖，每一次跨越，都始于对某个“微小细节”的死磕。 记得第一次带Lab-4“哈希表实现”时，学生普遍卡在“开放寻址法的删除操作”。教材说“删除后标记为DELETED”，但没人告诉你为什么不能直接置空。我带着学生一起写测试：插入key=100（哈希值h=5），再插入key=200（h=5，线性探测到6），此时删除key=100，若table[5]置空，则key=200再也无法被find找到（因为find遇到空就停止搜索）。这个“DELETED”标记，本质是告诉find函数：“这里曾经有东西，继续往后找”。那一刻，学生眼里的光，不是来自听懂了概念，而是亲手用enum Status {EMPTY, OCCUPIED, DELETED};把这个逻辑刻进了代码。

另一个深刻体会是：“能跑”和“健壮”之间，隔着一百次core dumped。 Final Exam.cpp之所以不给完整答案，是因为真正的编程能力，是在无数次Segmentation Fault后，学会用gdb看寄存器、用valgrind查内存、用strace追系统调用。我至今记得一个学生，在Lab-2中为stack类写了完美的push/pop，却在display函数里忘了if (isEmpty()) return;，导致空栈top()崩溃。他花了三小时，最后在gdb里单步到top()函数，看到this->top_ptr是0x0，才真正理解“空指针”不是抽象概念，而是内存地址0x0。这种认知，任何PPT都无法传递。

所以，别急着把所有代码复制粘贴跑起来。打开Lab-1/student.cpp，删掉delete[] name;，编译运行，用valgrind看内存泄漏报告；打开Homework-by-C++/Homework-Week-5/bracket.cpp，注释掉if (st.empty()) return false;，输入)，看std::stack::top()如何抛异常。这些“自虐式”操作，才是把知识焊进肌肉记忆的唯一方式。这套资料的价值，不在于它提供了多少代码，而在于它为你标记出了所有值得“自虐”的坐标——那些在深夜调试时，让你拍桌大喊“原来如此！”的瞬间，才是数据结构真正活过来的时刻。

本文还有配套的精品资源，点击获取 menu-r.4af5f7ec.gif

简介：这套资料完整复现重庆大学2023年秋季《数据结构与算法》课程实操内容，直接对应课堂教学节奏。笔记用Markdown整理，覆盖线性结构、栈与队列、树、堆、图、查找与排序等全部核心模块，每部分都配C++可运行代码；PTA作业按周组织，C++版包含全部16周题目，Python版精选前9周重点题，方便对比同一算法在两种语言中的写法差异；4个上机实验（Lab-1至Lab-4）全部提供完整C++工程，含源码、编译说明和运行示例；期末考试编程题以Final Exam.cpp形式给出，可直接调试验证逻辑。所有文件按功能分类存放，目录清晰，支持快速定位——比如Homework-by-C++下是各周C++作业，Lab-by-C++里是四个实验项目，Introduction.md和README.md提供整体使用指引。配套有requirements.txt和app.py，部分Python作业可直接本地运行。适合自学查漏、考前刷题、代码速查或教学备课时调用具体实现。


本文还有配套的精品资源，点击获取
menu-r.4af5f7ec.gif

# 数据结构 # 算法
Logo
亚马逊云科技技术品牌专区

更多推荐

Kiro Editor 开发实战：使用 Cargo 构建、测试与性能优化指南

欢迎来到这篇终极指南，我们将深入探索如何使用Rust构建高性能的终端文本编辑器Kiro Editor。无论你是Rust新手还是经验丰富的开发者，这篇完整教程将带你了解如何利用Cargo工具链进行高效的开发、测试和性能优化，打造一款快速、轻量且功能强大的UTF-8文本编辑器。## 什么是Kiro Editor？Kiro Editor是一款使用Rust编写的极简终端文本编辑器，它最初是著名编辑

avatar 亚马逊云科技技术品牌专区

2026年量化工具选择，要跟着能力基础走

读者应理解，选择工具前要先判断自己的能力基础和当前任务。工具应该帮助自己补上当前最关键的缺口，而不是替代学习顺序本身。

avatar 亚马逊云科技技术品牌专区

近期零基础学量化，先按基础差异拆学习顺序

读者应明白，拆解学习顺序时要先看自己的基础缺口，再决定哪一段需要放慢。不同流程阶段都有不同检查任务，学习路线要能反映这些差异。

avatar 亚马逊云科技技术品牌专区