← C++ 教材目录（共 13 章）

第 10 章　动手写数据结构

red wenzi · 2026-09-15 · 编程语言 · C++ · 📖 预计阅读 40 分钟 · 共 7 道练习
🧮 这一章正在拆分：「单链表」部分已经整理成语言无关的 数据结构与算法 · 第 1 章 链表，给出 C / C++ / Java / Python 四语言对照（标准库写法 + 手写底层实现）与复杂度标注，四份代码实测可跑。「顺序表」部分会在数组那一章整理好后移过去 · 查看这条线的目录 →
🎯 本章你会学到：自己实现顺序表与单链表，并学会验证它。建议边读边敲代码，每节的练习先自己做，再展开答案对照。

本章把前面九章用起来：完整实现顺序表和单链表——它们分别代表“连续存储”和“链式存储”两条路线，把这两个写明白，后面的栈、队列、树、图都是它们的变形。

10.1 顺序表

顺序表 = 一段连续内存 + 边界纪律。工程写法用 std::vector 做底层，重点在接口设计和边界检查。

接口设计：能用 std::vector 就省下五法则

template <typename T> class ArrayList，用 std::vector<T> data_ 做底层。拷贝、析构自动正确（零法则），不需要手写任何特殊函数。需要提供：push_back、size、operator[]（返回 T& 支持读写）、at（带边界检查）。insert 前检查 pos > size() 抛 std::out_of_range——边界纪律必须在接口层守住。

示例代码
template <typename T>
class ArrayList {
public:
    void push_back(const T& v) { data_.push_back(v); }
    std::size_t size() const { return data_.size(); }
    T& operator[](std::size_t i) { return data_[i]; }
    void insert(std::size_t pos, const T& v) {
        if (pos > size()) { throw std::out_of_range("out of range"); }
        data_.insert(data_.begin() + static_cast<std::ptrdiff_t>(pos), v);
    }
private:
    std::vector<T> data_;
};
⚠️ 易错点　begin() + pos 要 static_cast<std::ptrdiff_t>：size_t 和迭代器差值的类型不同，混用会有符号警告。

自己管理数组时多出来的三件事

若作业要求不用 std::vector：① size_ 与 capacity_ 分开维护，容量不够时按 1.5~2 倍扩容；② 插入删除要搬移元素，用 std::move 比逐个赋值高效；③ 必须写析构（delete[] data_）、拷贝构造（新数组+复制）、拷贝赋值（处理自赋值）、移动构造/移动赋值——就是第 5 章的五法则。把 data_ 换成 T* data_ 自己补一遍五法则，是检验第 4、5 章是否真懂的最好方式。

⚠️ 易错点　顺序表插入/删除是 O(n)（元素搬移），随机访问 O(1)。

✍️ 本节练习

10.1.1必做迷你顺序表

基于 std::vector<T> 实现模板类 ArrayList：push_back、size、operator[]。main 里插入 1、3、5 三个数，用 [] 输出。

输入　无

输出　1 3 5

样例输入
（本题无输入）
样例输出
1 3 5

💡 提示　operator[] 返回 T& 支持读写。

✅ 查看参考答案与解析 
#include <iostream>
#include <vector>
template <typename T>
class ArrayList {
public:
    void push_back(const T& v) { data_.push_back(v); }
    std::size_t size() const { return data_.size(); }
    T& operator[](std::size_t i) { return data_[i]; }
private:
    std::vector<T> data_;
};
int main() {
    ArrayList<int> list;
    list.push_back(1);
    list.push_back(3);
    list.push_back(5);
    for (std::size_t i = 0; i < list.size(); ++i) {
        std::cout << list[i] << ' ';
    }
    std::cout << '\n';
    return 0;
}

解析　用 vector 做底层，拷贝/析构自动正确（零法则）。

10.1.2挑战带插入的顺序表

在 ArrayList 里加 insert(pos, value)：位置非法（pos > size）抛 std::out_of_range。main 里先 push 1、3，再 insert(1, 2) 变成 1 2 3 输出；再故意 insert(99, 9) 观察异常被捕获。

输入　无

输出　第一行 1 2 3；第二行 out of range。

样例输入
（本题无输入）
样例输出
1 2 3
out of range

💡 提示　insert 内部用 data_.insert(data_.begin() + pos, v)，注意 pos 转 ptrdiff_t。

✅ 查看参考答案与解析 
#include <iostream>
#include <stdexcept>
#include <vector>
template <typename T>
class ArrayList {
public:
    void push_back(const T& v) { data_.push_back(v); }
    void insert(std::size_t pos, const T& v) {
        if (pos > size()) { throw std::out_of_range("out of range"); }
        data_.insert(data_.begin() + static_cast<std::ptrdiff_t>(pos), v);
    }
    std::size_t size() const { return data_.size(); }
    T& operator[](std::size_t i) { return data_[i]; }
private:
    std::vector<T> data_;
};
int main() {
    ArrayList<int> list;
    list.push_back(1);
    list.push_back(3);
    list.insert(1, 2);
    for (std::size_t i = 0; i < list.size(); ++i) {
        std::cout << list[i] << ' ';
    }
    std::cout << '\n';
    try {
        list.insert(99, 9);
    }
    catch (const std::out_of_range& e) {
        std::cout << e.what() << '\n';
    }
    return 0;
}

解析　对外接口用异常报告错误；先检查再操作是顺序表的边界纪律。

10.2 单链表

链表的价值：插入删除不需要搬移元素（O(1)，前提是知道位置）。但要处理“表头”这个特殊情况，还要保证析构释放所有节点。

裸指针链表的两处特殊 + 析构纪律

教材常见的裸指针实现有三个必须注意的点：① 删除要维护 prev 指针——单链表只能单向走，删 cur 得让前一个节点跳过它；② insert/remove 都要单独处理“表头”这个特殊情况（prev == nullptr 时改 head_）；③ 析构必须 while 循环遍历释放所有节点，一个都不能漏。更优雅的解法是用哨兵头节点，把两种情况统一成一种。

示例代码
bool remove(const T& v) {
    Node* cur = head_; Node* prev = nullptr;
    while (cur != nullptr && cur->value != v) { prev = cur; cur = cur->next; }
    if (cur == nullptr) { return false; }
    if (prev == nullptr) { head_ = cur->next; }   // 删的是头节点
    else { prev->next = cur->next; }
    delete cur;
    return true;
}
⚠️ 易错点　默认拷贝会复制 head_ 指针：两个对象指向同一条链，析构释放两次。禁止拷贝（= delete）或写深拷贝。

unique_ptr 版链表：没有 delete 的写法

用 std::unique_ptr<Node> next 实现，head 析构时递归释放整条链，不需要写析构函数，也不会泄漏。注意：递归释放对超长链表会栈溢出，工程上处理超长链表会自己写循环释放，或干脆用 vector/deque。

示例代码
struct Node {
    T value;
    std::unique_ptr<Node> next;
};
std::unique_ptr<Node> head_;
// 没有析构函数：head_ 析构时递归释放整条链
⚠️ 易错点　结构没有绝对好坏，只有适不适合当前的数据规模和访问模式。随机访问和尾插用顺序表，频繁在已知位置增删用链表。
123prevcurnext先存 nextcur->next = prev三个指针整体右移口诀：存 next → 反指向 → 挪 prev/cur。漏掉任何一步断链，就是段错误。
图 5：链表就地反转的三指针顺序

✍️ 本节练习

10.2.1必做头插链表

实现单链表（裸指针版）的 pushFront、print、clear 和析构。main 里头插 1、2、3，打印后自动析构。

输入　无

输出　3 -> 2 -> 1 -> null

样例输入
（本题无输入）
样例输出
3 -> 2 -> 1 -> null

💡 提示　头插：新节点指向旧 head；析构必须遍历释放所有节点。

✅ 查看参考答案与解析 
#include <iostream>
template <typename T>
class LinkedList {
public:
    ~LinkedList() { clear(); }
    void pushFront(const T& v) {
        head_ = new Node{v, head_};
    }
    void clear() {
        while (head_ != nullptr) {
            Node* next = head_->next;
            delete head_;
            head_ = next;
        }
    }
    void print() const {
        for (Node* cur = head_; cur != nullptr; cur = cur->next) {
            std::cout << cur->value << " -> ";
        }
        std::cout << "null\n";
    }
private:
    struct Node { T value; Node* next; };
    Node* head_ = nullptr;
};
int main() {
    LinkedList<int> list;
    list.pushFront(1);
    list.pushFront(2);
    list.pushFront(3);
    list.print();
    return 0;
}

解析　先存 next 再 delete 当前节点，逐个释放；漏掉循环就泄漏。

10.2.2挑战就地反转

在链表中加 void reverse()：就地反转链表（三指针）。main 里头插 1、2、3（链表为 3->2->1），反转后打印（1->2->3）。

输入　无

输出　1 -> 2 -> 3 -> null

样例输入
（本题无输入）
样例输出
1 -> 2 -> 3 -> null

💡 提示　三指针 prev/cur/next：先存 next，再 cur->next = prev，整体前进。

✅ 查看参考答案与解析 
#include <iostream>
template <typename T>
class LinkedList {
public:
    ~LinkedList() { clear(); }
    void pushFront(const T& v) { head_ = new Node{v, head_}; }
    void reverse() {
        Node* prev = nullptr;
        Node* cur = head_;
        while (cur != nullptr) {
            Node* next = cur->next;   // 先存下一个
            cur->next = prev;         // 改指向
            prev = cur;
            cur = next;
        }
        head_ = prev;
    }
    void clear() {
        while (head_ != nullptr) {
            Node* next = head_->next;
            delete head_;
            head_ = next;
        }
    }
    void print() const {
        for (Node* cur = head_; cur != nullptr; cur = cur->next) {
            std::cout << cur->value << " -> ";
        }
        std::cout << "null\n";
    }
private:
    struct Node { T value; Node* next; };
    Node* head_ = nullptr;
};
int main() {
    LinkedList<int> list;
    list.pushFront(1);
    list.pushFront(2);
    list.pushFront(3);   // 3 -> 2 -> 1
    list.reverse();
    list.print();        // 1 -> 2 -> 3
    return 0;
}

解析　就地反转是链表经典题：三指针缺一不可，顺序不能乱。

10.3 调试与验证：让错误自己暴露

手写数据结构最大的困难是“错了但不报错”：链表断链、数组越界、忘记释放，程序往往不崩溃，只是结果悄悄不对。所以要把下面这套流程变成习惯。

四件套流程

① 编译打开 -Wall -Wextra -Wpedantic；② 用 assert 把不变量写下来（assert(size_ <= capacity_)），断言既是文档也是测试，-DNDEBUG 在发布版关掉；③ 小数据规模手动验证：先测空容器、一个元素、两个元素，绝大多数边界错误都在这里；④ 用 -fsanitize=address,undefined 跑一遍，直接定位越界、泄漏和未定义行为。

⚠️ 易错点　sanitizer 只在调试期开，会拖慢程序，不要带上线。

随机对拍：最有效的自动化验证

写一个随机测试，把同样的操作序列同时作用在你的结构和 std::vector/std::list 上，每次操作后 assert 两边 size 相等、逐个元素相等。固定随机种子（std::mt19937 gen(12345)）方便复现。十几行随机测试，比反复读代码找错高效得多。

示例代码
std::mt19937 gen(12345);
std::uniform_int_distribution<int> op(0, 2);
for (int step = 0; step < 10000; ++step) {
    int action = op(gen);
    // switch (action) { case 0: mine.pushBack(x); ref.push_back(x); break; ... }
    // assert(mine.size() == reference.size());
    // 逐个元素比较，相等则继续
}
⚠️ 易错点　数据结构作业评分往往只看通过测试用例的数量，对拍测试是性价比最高的提分方式。

✍️ 本节练习

10.3.1必做越界抓现行

写一个越界访问的坏程序：int a[5] 循环 i <= 5 访问 a[i]。用 g++ -fsanitize=address,undefined 编译运行，观察它打印的越界报错（第几行、读写几个字节）。然后把循环改成 i < 5，确认零报错。

输入　无

输出　正常运行后输出 12345。

样例输入
（本题无输入）
样例输出
12345

💡 提示　坏版本运行时会打印 AddressSanitizer 报错；好版本只有 12345。

✅ 查看参考答案与解析 
#include <iostream>
int main() {
    int a[5]{1, 2, 3, 4, 5};
    for (int i = 0; i < 5; ++i) {   // 好版本：i < 5
        std::cout << a[i];
    }
    std::cout << '\n';
    return 0;
}
// 坏版本（改成 i <= 5 后用 sanitizer 编译运行）：
// g++ -std=c++17 -g -fsanitize=address,undefined -o app app.cpp

解析　AddressSanitizer 会精确报出越界位置，这是新手阶段回报最高的工具。

10.3.2挑战随机对拍

写一个随机对拍程序：固定种子生成 1000 对随机数，你的 max 函数和标准答案（条件运算符）比对，不一致就报错退出。

输入　无

输出　stress test passed

样例输入
（本题无输入）
样例输出
stress test passed

💡 提示　std::mt19937 gen(12345) 固定种子保证可复现。

✅ 查看参考答案与解析 
#include <cassert>
#include <iostream>
#include <random>
int myMax(int a, int b) { return a > b ? a : b; }
int main() {
    std::mt19937 gen(12345);
    std::uniform_int_distribution<int> dist(-100, 100);
    for (int step = 0; step < 1000; ++step) {
        int a = dist(gen), b = dist(gen);
        int got = myMax(a, b);
        int expect = (a > b ? a : b);
        assert(got == expect);
    }
    std::cout << "stress test passed\n";
    return 0;
}

解析　对拍 = 你的实现 vs 标准实现跑同样输入再比较；写数据结构时这是最有效的自动化验证。

本章小结

🧩 本章综合练习

这几道题把本章多个知识点串起来，建议合上资料独立完成，再展开答案对照。

10.A综合unique_ptr 版单链表 + 随机对拍

用 std::unique_ptr 实现单链表（pushFront / pushBack / reverse / print / size），全程不写析构函数；再用固定随机种子做 1000 轮随机对拍，断言链表和 std::vector 的 size 与元素逐一相等。

输入　第一行整数 n；第二行 n 个整数（依次 pushBack 进链表）。

输出　第一行输出反转后的链表内容；第二行输出 stress test passed。

样例输入
4
1 2 3 4
样例输出
4 -> 3 -> 2 -> 1 -> null
stress test passed

💡 提示　节点的 next 是 unique_ptr，交接所有权一律用 std::move；反转时用三个 unique_ptr 轮换，不要手写 delete。

✅ 查看参考答案与解析 
#include <cassert>
#include <cstddef>
#include <iostream>
#include <memory>
#include <random>
#include <vector>

struct Node {
    int value{};
    std::unique_ptr<Node> next;
    explicit Node(int v) : value(v) { }
};

class List {
public:
    void pushFront(int v) {
        auto n = std::make_unique<Node>(v);
        n->next = std::move(head_);
        head_ = std::move(n);
        ++size_;
    }

    void pushBack(int v) {
        auto n = std::make_unique<Node>(v);
        if (!head_) {
            head_ = std::move(n);
        } else {
            Node* cur = head_.get();
            while (cur->next) { cur = cur->next.get(); }
            cur->next = std::move(n);
        }
        ++size_;
    }

    void reverse() {                      // 就地反转
        std::unique_ptr<Node> prev;
        while (head_) {
            std::unique_ptr<Node> cur = std::move(head_);
            head_ = std::move(cur->next);
            cur->next = std::move(prev);
            prev = std::move(cur);
        }
        head_ = std::move(prev);
    }

    std::size_t size() const { return size_; }

    std::vector<int> toVector() const {
        std::vector<int> out;
        for (const Node* p = head_.get(); p != nullptr; p = p->next.get()) {
            out.push_back(p->value);
        }
        return out;
    }

    void print() const {
        for (const Node* p = head_.get(); p != nullptr; p = p->next.get()) {
            std::cout << p->value << " -> ";
        }
        std::cout << "null\n";
    }

private:
    std::unique_ptr<Node> head_;
    std::size_t size_ = 0;
};

int main() {
    int n{};
    std::cin >> n;
    List list;
    for (int i = 0; i < n; ++i) {
        int x{};
        std::cin >> x;
        list.pushBack(x);
    }
    list.reverse();
    list.print();

    std::mt19937 gen(20260914);                      // 固定种子，可复现
    std::uniform_int_distribution<int> dist(-50, 50);
    for (int round = 0; round < 1000; ++round) {
        List mine;
        std::vector<int> ref;
        for (int k = 0; k < 20; ++k) {
            int x = dist(gen);
            mine.pushBack(x);
            ref.push_back(x);
            assert(mine.size() == ref.size());
            assert(mine.toVector() == ref);           // 和标准容器对拍
        }
    }
    std::cout << "stress test passed\n";
    return 0;
}

解析　head_ 析构时会递归释放整条链，所以不必写析构函数；链表极长时递归释放可能爆栈，工程上会改成循环释放。

📚 本文概念都在知识大全：

链表 · 栈与队列 · Sanitizer · 单元测试

← 上一章：第 9 章 现代 C++ 特性下一章：第 11 章 十个算法思想 →