C++ 练习册第 10 章动手写数据结构

📝 本章练习：12 题（A 识别 / B 理解 / C 改错 / D 写程序）。先自己做完再看答案——A、B 档不翻书做，C、D 档必须真的编译运行。

10.1 顺序表

A1识别判断题：vector 的 push_back 平摊复杂度是 O(1)。

答：______________

✅ 查看答案与解析

答案　对

解析：因为扩容按 1.5~2 倍指数增长，平摊到每次 push_back 是 O(1)。

B1理解选择题：顺序表在头部 insert 一个元素的时间复杂度是？

O(1)

O(log n)

O(n)

O(n^2)

答：______________

✅ 查看答案与解析

答案　C

解析：插入位置之后的元素要整体后移，所以是 O(n)。

C1应用改错题：下面 pop_back 在空表上调用，会越界或崩溃。

void pop_back() {
    data_.pop_back();   // 空表时未定义行为
}

✅ 查看答案与解析

答案　先检查再操作：

解析：对外的接口用异常或返回值报告错误；内部实现用 assert 暴露 bug。

void pop_back() {
    if (empty()) { throw std::out_of_range("pop_back on empty list"); }
    data_.pop_back();
}

D1创造写程序：手写一个简化 ArrayList（基于 std::vector<T>），实现 push_back、insert(pos, value)（越界抛异常）、size，main 里插入 3 个数输出。

提示：insert 前检查 pos > size() 就抛 out_of_range。

✅ 查看答案与解析

答案　参考答案：

解析：用 std::vector 做底层就自动获得正确的拷贝/析构行为（零法则）。

#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("insert position"); }
        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);           // 1 2 3
    for (std::size_t i = 0; i < list.size(); ++i) { std::cout << list[i] << ' '; }
    std::cout << '\n';           // 1 2 3
    return 0;
}

10.2 单链表

A1识别判断题：单链表删除节点时，删除头节点要特殊处理。

答：______________

✅ 查看答案与解析

答案　对

解析：删头 = 让 head_ 指向第二个节点；删中间需要维护 prev 指针。更优雅：用带头节点（哨兵节点）统一两种情况。

B1理解选择题：就地反转单链表需要几个指针（前驱、当前、后继）？

1 个

2 个

3 个

4 个

答：______________

✅ 查看答案与解析

答案　C

解析：经典三指针：prev、cur、next。先存 next，再改 cur->next = prev，然后整体前进。

C1应用改错题：下面析构只删了头节点，其余节点全部泄漏。

~LinkedList() { delete head_; }   // 只删了一个节点

✅ 查看答案与解析

答案　遍历释放全部节点：

解析：先存 next 再 delete 当前节点，逐个走完整条链。

~LinkedList() { clear(); }
void clear() {
    while (head_ != nullptr) {
        Node* next = head_->next;
        delete head_;
        head_ = next;
    }
    size_ = 0;
}

D1创造写程序：实现单链表（裸指针版）的 pushFront、print、clear，main 里头插 3 个数并打印。

提示：Node 结构含 value 和 next；头插新节点指向旧 head。

✅ 查看答案与解析

答案　参考答案：

解析：头插 O(1)；析构必须遍历释放所有节点，否则泄漏。

#include <iostream>
template <typename T>
class LinkedList {
public:
    ~LinkedList() { clear(); }
    void pushFront(const T& v) {
        head_ = new Node{v, head_};
        ++size_;
    }
    void clear() {
        while (head_ != nullptr) {
            Node* next = head_->next;
            delete head_;
            head_ = next;
        }
        size_ = 0;
    }
    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;
    std::size_t size_ = 0;
};
int main() {
    LinkedList<int> list;
    list.pushFront(1);
    list.pushFront(2);
    list.pushFront(3);
    list.print();   // 3 -> 2 -> 1 -> null
    return 0;
}

10.3 调试与对拍

A1识别判断题：g++ -fsanitize=address,undefined 能精确定位越界、泄漏和未定义行为。

答：______________

✅ 查看答案与解析

答案　对

解析：AddressSanitizer 直接告诉你“第 27 行越界写 4 字节”“第 15 行申请的内存泄漏了”，写数据结构作业前先跑一遍。

B1理解选择题：编译时加哪个宏可以关闭 assert？

-DNDEBUG

-DDEBUG

-O0

-Werror

答：______________

✅ 查看答案与解析

答案　A

解析：-DNDEBUG 定义 NDEBUG，assert 全部失效，用于发布版本。

C1应用改错题：下面代码越界访问，sanitizer 会立刻报错。

int a[5]{1, 2, 3, 4, 5};
for (int i = 0; i <= 5; ++i) { std::cout << a[i]; }   // i=5 越界！

✅ 查看答案与解析

答案　for (int i = 0; i < 5; ++i) { std::cout << a[i]; } // 改成 < 5

解析：数组下标合法范围是 0..4。写 <= 5 就会越界读。

D1创造写程序：写一个“随机对拍”骨架——固定种子生成 1000 个随机数，你的函数（比如手写 max）和标准答案比较，不一致就报错。

提示：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;
}

📚 相关概念：编译与链接 · STL · map / set · 迭代器

← 第 9 章第 11 章 →