线性表 ADT 的实现

参考实现与适用范围 本页保留四个实验任务，代码按下述明确契约修正。附件提供可编译实现和自测；未找回的下发题面与评测文件仍待核，不把参考实现宣称为原评测通过版本。

实验 2: 线性表实现及应用 #

任务 1: 为指定的 List ADT 实现各种数据结构 #

操作契约与实现范围 #

下面三种表示保留相同的操作名，分别命名为 ArrayList、SinglyList、DoublyList，便于在同一测试中比较。此处明确参考实现的行为；原实验的完整 ADT 头文件、list_testcase.txt 与期望输出仍待找回，不能据本文断言兼容下发评测。

操作	本文约定
初始化	`init(length)` 接受非负整数，清空已有元素；负数抛出 `invalid_argument`，不改变现有表。未初始化与容量为 0 的表为空且不可插入。
插入、删除、替换	成功返回 `true`，空表删除/替换或满表插入返回 `false`。插入在当前元素之后，并选中新元素；空表插入首元素。删除后选择原后继，删除尾元素则回到表头，删空后光标为 `-1`。
光标移动与读取	`gotoBeginning/End/Next/Prev` 失败不越界；`getCursor()` 返回 `optional<T>`，空表是 `nullopt`，不再用 `0` 或 `nullptr` 冒充元素。
查找	保留现存三个实现一致的行为：从当前光标向尾部查找，成功停在匹配元素，失败停在尾部；空表失败，不循环回表头。原下发接口是否同此仍待核。
移动元素	`moveToNth(n)` 在本文以移动后的 0 基下标为准，合法范围为 `[0, size()-1]`；选中被移动的元素，其他元素保持相对顺序。空表、负数、越界返回 `false` 且不改变表。原稿各表示的下标行为不一致，因此这是显式参考契约，不是假定的原评测规则。
容量	数组 `capacity()` 是固定槽位数；链表 `capacity()` 是实际结点数，等于 `size()`。另用 `limit()` 表示 `init` 设置的插入上限，避免把结点数与上限混为一谈。
生命周期	对象从构造时即有效；链式表示在 `clear`、重复 `init` 和析构时释放结点，所有表示禁用复制和移动，防止无意的浅拷贝或失效的移后状态。分配失败使用标准异常，不吞掉异常。

元素需支持本文所用的复制、赋值和相等比较，顺序数组还要求默认构造；测试包含 int、char 和 std::string。不承诺用户自定义元素在复制/赋值抛异常时的强异常保证。输出放在独立的 showStructure 中，只在需要打印时要求元素可写入流，不在 ADT 内假定字符类型。

代码、两个命令行驱动及回归测试可从完整附件下载；附件说明列出编译命令和输入输出。下面各段对应附件中的同一份实现。

代码实现 #

顺序数组 #

#pragma once
#include <algorithm>
#include <optional>
#include <stdexcept>
#include <vector>

template<class T>
class ArrayList {
    std::vector<T> val_;
    int cursor_ = -1, len_ = 0;
public:
    ArrayList() = default;
    ArrayList(const ArrayList&) = delete;
    ArrayList& operator=(const ArrayList&) = delete;
    void init(int length) {
        if (length < 0) throw std::invalid_argument("negative capacity");
        std::vector<T> fresh(static_cast<std::size_t>(length));
        val_.swap(fresh);
        len_ = 0;
        cursor_ = -1;
    }
    bool isEmpty() const { return len_ == 0; }
    bool isFull() const { return len_ == limit(); }
    int size() const { return len_; }
    int capacity() const { return limit(); }
    int limit() const { return static_cast<int>(val_.size()); }
    int cursorIndex() const { return cursor_; }
    bool insert(const T& value) {
        if (isFull()) return false;
        T copy = value;
        for (int i = len_; i > cursor_ + 1; --i) val_[i] = val_[i - 1];
        val_[cursor_ + 1] = copy;
        ++len_;
        ++cursor_;
        return true;
    }
    bool remove() {
        if (isEmpty()) return false;
        for (int i = cursor_; i + 1 < len_; ++i) val_[i] = val_[i + 1];
        --len_;
        if (len_ == 0) cursor_ = -1;
        else if (cursor_ == len_) cursor_ = 0;
        return true;
    }
    bool replace(const T& value) {
        if (isEmpty()) return false;
        val_[cursor_] = value;
        return true;
    }
    // Logical clear retains the fixed array slots until init/destruction.
    void clear() { len_ = 0; cursor_ = -1; }
    bool gotoBeginning() {
        if (isEmpty()) return false;
        cursor_ = 0;
        return true;
    }
    bool gotoEnd() {
        if (isEmpty()) return false;
        cursor_ = len_ - 1;
        return true;
    }
    bool gotoNext() {
        if (isEmpty() || cursor_ + 1 == len_) return false;
        ++cursor_;
        return true;
    }
    bool gotoPrev() {
        if (isEmpty() || cursor_ == 0) return false;
        --cursor_;
        return true;
    }
    std::optional<T> getCursor() const {
        if (isEmpty()) return std::nullopt;
        return val_[cursor_];
    }
    bool moveToNth(int n) {
        if (n < 0 || n >= len_) return false;
        if (n < cursor_)
            std::rotate(val_.begin() + n, val_.begin() + cursor_,
                        val_.begin() + cursor_ + 1);
        else if (n > cursor_)
            std::rotate(val_.begin() + cursor_, val_.begin() + cursor_ + 1,
                        val_.begin() + n + 1);
        cursor_ = n;
        return true;
    }
    bool find(const T& value) {
        if (isEmpty()) return false;
        while (val_[cursor_] != value && gotoNext()) {}
        return val_[cursor_] == value;
    }
    std::vector<T> values() const { return {val_.begin(), val_.begin() + len_}; }
    bool invariant() const {
        return len_ >= 0 && len_ <= limit() &&
               (len_ == 0 ? cursor_ == -1 : cursor_ >= 0 && cursor_ < len_);
    }
};

共用字符指令驱动 #

使用 std::getline 逐行读取，不再使用固定字符数组与 gets。+x 插入字符，=x 替换当前字符；- # * > < ~ 分别为删除、表头、表尾、后继、前驱和清空。参数可与命令间隔空白，但必须是一个可打印的非空白 ASCII 字符。

每行先完成语法检查，缺参数、未知命令或超过 200000 字节的行不执行；合法行中的单次操作失败会报告错误且保持该操作前的状态，后续指令仍继续。驱动返回 0 表示成功、2 表示输入或操作被拒绝，不再静默假装成功。

#pragma once
#include <cctype>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

struct ListCommand { char op; char value = 0; };

inline std::vector<ListCommand> parse_list_commands(const std::string& line) {
    if (line.size() > 200000) throw std::invalid_argument("line too long");
    std::vector<ListCommand> commands;
    for (std::size_t i = 0; i < line.size(); ++i) {
        const char op = line[i];
        if (std::isspace(static_cast<unsigned char>(op))) continue;
        if (op == '+' || op == '=') {
            do { ++i; } while (i < line.size() &&
                std::isspace(static_cast<unsigned char>(line[i])));
            if (i == line.size()) throw std::invalid_argument("missing character argument");
            const auto value = static_cast<unsigned char>(line[i]);
            if (value < 33 || value > 126) throw std::invalid_argument("expected ASCII character");
            commands.push_back({op, line[i]});
        } else if (std::string("-#*><~").find(op) != std::string::npos) {
            commands.push_back({op, 0});
        } else throw std::invalid_argument("unknown command");
    }
    return commands;
}

template<class List>
bool execute_list_command(List& list, const ListCommand& c) {
    switch (c.op) {
        case '+': return list.insert(c.value);
        case '-': return list.remove();
        case '=': return list.replace(c.value);
        case '#': return list.gotoBeginning();
        case '*': return list.gotoEnd();
        case '>': return list.gotoNext();
        case '<': return list.gotoPrev();
        case '~': list.clear(); return true;
        default: throw std::invalid_argument("unknown command");
    }
}

template<class List>
void showStructure(const List& list, std::ostream& out) {
    if (list.isEmpty()) out << "Empty list ";
    else for (const auto& value : list.values()) out << value << ' ';
    out << "{capacity = " << list.capacity() << ", length = " << list.size()
        << ", cursor = " << list.cursorIndex() << ", limit = " << list.limit() << "}\n";
}

template<class List>
int run_list_commands(std::istream& input, std::ostream& out, std::ostream& errors) {
    List list;
    list.init(512);
    std::string line;
    std::size_t number = 0;
    bool failed = false;
    while (std::getline(input, line)) {
        ++number;
        try {
            const auto commands = parse_list_commands(line);
            for (const auto& c : commands) {
                if (!execute_list_command(list, c)) {
                    errors << "line " << number << ": rejected operation " << c.op << '\n';
                    failed = true;
                }
            }
            showStructure(list, out);
        } catch (const std::invalid_argument& e) {
            errors << "line " << number << ": " << e.what() << '\n';
            failed = true;
        }
    }
    if (input.bad()) throw std::runtime_error("input read failed");
    return failed ? 2 : 0;
}

下面的 main 替代原来写死 freopen 的驱动。保留 list_testcase.txt 这一输入文件名作为可选重定向来源，而不假定文件一定存在；输出位置由运行命令指定。

#include "array_list.hpp"
#include "singly_list.hpp"
#include "doubly_list.hpp"
#include "list_commands.hpp"

int main(int argc, char** argv) {
    try {
        const std::string mode = argc == 2 ? argv[1] : "array";
        if (argc > 2) throw std::invalid_argument("usage: list_demo [array|single|double]");
        if (mode == "array") return run_list_commands<ArrayList<char>>(std::cin, std::cout, std::cerr);
        if (mode == "single") return run_list_commands<SinglyList<char>>(std::cin, std::cout, std::cerr);
        if (mode == "double") return run_list_commands<DoublyList<char>>(std::cin, std::cout, std::cerr);
        throw std::invalid_argument("unknown list implementation");
    } catch (const std::exception& e) {
        std::cerr << "error: " << e.what() << '\n';
        return 2;
    }
}

输入：
+a+b
#=c

array 模式输出：
a b {capacity = 512, length = 2, cursor = 1, limit = 512}
c b {capacity = 512, length = 2, cursor = 0, limit = 512}

链表模式的上述两行 capacity 均为 2，其余状态一致。驱动有意同时显示 limit，不是按未知的下发文件格式伪造输出。

单向链表 #

使用上面的共用驱动，选择 single 模式；类名区分表示，操作契约不变。

#pragma once
#include <optional>
#include <stdexcept>
#include <vector>

template<class T>
class SinglyList {
    struct Point { T val; Point* next; };
    Point* head_ = nullptr;
    Point* p_ = nullptr;
    int cursor_ = -1, len_ = 0, limit_ = 0;
    Point* at(int n) const {
        Point* q = head_;
        while (n-- > 0) q = q->next;
        return q;
    }
public:
    SinglyList() = default;
    SinglyList(const SinglyList&) = delete;
    SinglyList& operator=(const SinglyList&) = delete;
    ~SinglyList() { clear(); }
    void init(int length) {
        if (length < 0) throw std::invalid_argument("negative limit");
        clear();
        limit_ = length;
    }
    bool isEmpty() const { return len_ == 0; }
    bool isFull() const { return len_ == limit_; }
    int size() const { return len_; }
    int capacity() const { return len_; }
    int limit() const { return limit_; }
    int cursorIndex() const { return cursor_; }
    bool insert(const T& value) {
        if (isFull()) return false;
        Point* fresh = new Point{value, p_ ? p_->next : nullptr};
        if (p_) p_->next = fresh;
        else head_ = fresh;
        p_ = fresh;
        ++len_;
        ++cursor_;
        return true;
    }
    bool remove() {
        if (isEmpty()) return false;
        Point* old = p_;
        Point* next = old->next;
        if (old == head_) head_ = next;
        else at(cursor_ - 1)->next = next;
        --len_;
        if (len_ == 0) { p_ = nullptr; cursor_ = -1; }
        else if (next) p_ = next;
        else { p_ = head_; cursor_ = 0; }
        delete old;
        return true;
    }
    bool replace(const T& value) {
        if (isEmpty()) return false;
        p_->val = value;
        return true;
    }
    void clear() noexcept {
        while (head_) {
            Point* old = head_;
            head_ = head_->next;
            delete old;
        }
        p_ = nullptr;
        len_ = 0;
        cursor_ = -1;
    }
    bool gotoBeginning() {
        if (isEmpty()) return false;
        p_ = head_;
        cursor_ = 0;
        return true;
    }
    bool gotoEnd() {
        if (isEmpty()) return false;
        while (gotoNext()) {}
        return true;
    }
    bool gotoNext() {
        if (!p_ || !p_->next) return false;
        p_ = p_->next;
        ++cursor_;
        return true;
    }
    bool gotoPrev() {
        if (cursor_ <= 0) return false;
        p_ = at(cursor_ - 1);
        --cursor_;
        return true;
    }
    std::optional<T> getCursor() const {
        if (!p_) return std::nullopt;
        return p_->val;
    }
    bool moveToNth(int n) {
        if (n < 0 || n >= len_) return false;
        if (n == cursor_) return true;
        Point* moving = p_;
        if (cursor_ == 0) head_ = moving->next;
        else at(cursor_ - 1)->next = moving->next;
        // n is the final zero-based position, after unlinking this node.
        if (n == 0) { moving->next = head_; head_ = moving; }
        else {
            Point* previous = at(n - 1);
            moving->next = previous->next;
            previous->next = moving;
        }
        cursor_ = n;
        return true;
    }
    bool find(const T& value) {
        if (isEmpty()) return false;
        while (p_->val != value && gotoNext()) {}
        return p_->val == value;
    }
    std::vector<T> values() const {
        std::vector<T> out;
        for (Point* q = head_; q; q = q->next) out.push_back(q->val);
        return out;
    }
    bool invariant() const {
        if (len_ < 0 || len_ > limit_) return false;
        if (!len_) return !head_ && !p_ && cursor_ == -1;
        if (cursor_ < 0 || cursor_ >= len_) return false;
        int count = 0;
        for (Point* q = head_; q; q = q->next) {
            if (count >= len_ || (count == cursor_ && q != p_)) return false;
            ++count;
        }
        return count == len_;
    }
};

双向链表 #

#pragma once
#include <optional>
#include <stdexcept>
#include <vector>

template<class T>
class DoublyList {
    struct Point { T val; Point* next; Point* pre; };
    Point* head_ = nullptr;
    Point* p_ = nullptr;
    int cursor_ = -1, len_ = 0, limit_ = 0;
    Point* at(int n) const {
        Point* q = head_;
        while (n-- > 0) q = q->next;
        return q;
    }
public:
    DoublyList() = default;
    DoublyList(const DoublyList&) = delete;
    DoublyList& operator=(const DoublyList&) = delete;
    ~DoublyList() { clear(); }
    void init(int length) {
        if (length < 0) throw std::invalid_argument("negative limit");
        clear();
        limit_ = length;
    }
    bool isEmpty() const { return len_ == 0; }
    bool isFull() const { return len_ == limit_; }
    int size() const { return len_; }
    int capacity() const { return len_; }
    int limit() const { return limit_; }
    int cursorIndex() const { return cursor_; }
    bool insert(const T& value) {
        if (isFull()) return false;
        Point* fresh = new Point{value, p_ ? p_->next : nullptr, p_};
        if (p_) p_->next = fresh;
        else head_ = fresh;
        if (fresh->next) fresh->next->pre = fresh;
        p_ = fresh;
        ++len_;
        ++cursor_;
        return true;
    }
    bool remove() {
        if (isEmpty()) return false;
        Point* old = p_;
        Point* next = old->next;
        if (old->pre) old->pre->next = next;
        else head_ = next;
        if (next) next->pre = old->pre;
        --len_;
        if (!len_) { p_ = nullptr; cursor_ = -1; }
        else if (next) p_ = next;
        else { p_ = head_; cursor_ = 0; }
        delete old;
        return true;
    }
    bool replace(const T& value) {
        if (isEmpty()) return false;
        p_->val = value;
        return true;
    }
    void clear() noexcept {
        while (head_) {
            Point* old = head_;
            head_ = head_->next;
            delete old;
        }
        p_ = nullptr;
        len_ = 0;
        cursor_ = -1;
    }
    bool gotoBeginning() {
        if (isEmpty()) return false;
        p_ = head_;
        cursor_ = 0;
        return true;
    }
    bool gotoEnd() {
        if (isEmpty()) return false;
        while (gotoNext()) {}
        return true;
    }
    bool gotoNext() {
        if (!p_ || !p_->next) return false;
        p_ = p_->next;
        ++cursor_;
        return true;
    }
    bool gotoPrev() {
        if (!p_ || !p_->pre) return false;
        p_ = p_->pre;
        --cursor_;
        return true;
    }
    std::optional<T> getCursor() const {
        if (!p_) return std::nullopt;
        return p_->val;
    }
    bool moveToNth(int n) {
        if (n < 0 || n >= len_) return false;
        if (n == cursor_) return true;
        Point* moving = p_;
        if (moving->pre) moving->pre->next = moving->next;
        else head_ = moving->next;
        if (moving->next) moving->next->pre = moving->pre;
        Point* previous = n == 0 ? nullptr : at(n - 1);
        moving->pre = previous;
        moving->next = previous ? previous->next : head_;
        if (moving->next) moving->next->pre = moving;
        if (previous) previous->next = moving;
        else head_ = moving;
        cursor_ = n;
        return true;
    }
    bool find(const T& value) {
        if (isEmpty()) return false;
        while (p_->val != value && gotoNext()) {}
        return p_->val == value;
    }
    std::vector<T> values() const {
        std::vector<T> out;
        for (Point* q = head_; q; q = q->next) out.push_back(q->val);
        return out;
    }
    bool invariant() const {
        if (len_ < 0 || len_ > limit_) return false;
        if (!len_) return !head_ && !p_ && cursor_ == -1;
        if (cursor_ < 0 || cursor_ >= len_) return false;
        int count = 0;
        Point* previous = nullptr;
        for (Point* q = head_; q; q = q->next) {
            if (count >= len_ || q->pre != previous ||
                (count == cursor_ && q != p_)) return false;
            previous = q;
            ++count;
        }
        return count == len_;
    }
};

原练习记录称，曾用 fc 比较程序输出与实验下发文件，结果无差异。完整测试输入、预期输出和编译环境未附于本页，不能据此替代当前的代码安全验证。

现存题意记录称链式 capacity 是实际结点数；本实现据此输出 size()，并将插入上限另记为 limit()。原稿曾硬编码 512 来比较数组输出，这不能证明链表容量契约正确；原评测格式仍待核。

代码差异分析 #

与存储方式直接相关的基本操作是结点/槽位的插入、删除和光标定位。find、gotoEnd 等操作可由基本操作组合，但“抽象操作相同”不代表三种表示的实现文本完全相同。

moveToNth 必须同时满足元素顺序、目标下标和光标状态契约：数组用区间旋转，链表用摘链后重新接入。这样移动时不需要先删除元素再新分配结点，也不会因新分配失败而丢失被移动的值。

单向和双向链表不仅 gotoPrev 不同，插入、删除、移动结点时的反向链接也必须一起维护。双向链表的不变量包括表头前驱为空，以及每条 next/pre 链接互为对应；测试逐操作检查这些关系。

不同存储方式复杂度分析 #

令 n 为当前长度，假设元素的复制、赋值、比较及析构为常数时间；下表是本页实现的最坏时间，不把诊断用 invariant() 算进正常操作。

函数	顺序数组	单向链表	双向链表
`insert`	O(n)	O(1)	O(1)
`remove`	O(n)	O(n)	O(1)
`replace`	O(1)	O(1)	O(1)
`clear`	O(1)，逻辑清空	O(n)	O(n)
`isEmpty`	O(1)	O(1)	O(1)
`isFull`	O(1)	O(1)	O(1)
`gotoBeginning`	O(1)	O(1)	O(1)
`gotoEnd`	O(1)	O(n)	O(n)
`gotoNext`	O(1)	O(1)	O(1)
`gotoPrev`	O(1)	O(n)	O(1)
`getCursor`	O(1)	O(1)	O(1)
`showStructure`	O(n)	O(n)	O(n)
`moveToNth`	O(n)	O(n)	O(n)
`find`	O(n)	O(n)	O(n)

一些小细节及分析：

顺序数组的 clear 只清光标与逻辑长度，槽位对象仍存在，其资源到重新初始化或对象析构时才释放。这不是“释放所有元素资源”的清空语义。链式表示立即逐结点析构；showStructure 为输出调用 values() 建立副本，另需 O(n) 辅助空间。
moveToNth 的数组开销来自移动区间内元素；链式开销主要来自定位目标前驱。已知双链结点后，摘链与接回均为 O(1)。
单链表删除当前非首结点需从头定位前驱，双链表可直接取 pre，所以删除复杂度不同；这不意味着所有指针维护代码都相同。
如果给 List 额外维护尾指针，可将 gotoEnd 降至 O(1)，但插入、删除和移动时必须同步维护它。本页 List 保持原来的无尾指针设计，DQueue 则维护两端。
数组仍有常数时间随机定位、连续存储和缓存局部性优势；链表的动态结点、指针与分配也有成本。不能仅凭此表断言一种表示全面更优。

任务 2: 为指定的 DQueue ADT 实现两种数据结构 #

双端队列契约 #

init(length) 要求正容量，0 和负数抛出 invalid_argument 且保留原队列。构造后的空对象不能入队，须先初始化；入队满时返回 false，出队和读取空队列返回 nullopt。合法的 0、空字符串等元素不会与空队列混淆。

循环数组只维护队首与长度，队尾位置由两者计算，所有取模都在非零容量下进行。链式队列始终满足：空队列的 head、tail 同为空；非空时 head->pre 与 tail->next 为空；相邻链接双向一致。两端删除最后一个元素时会同步清空两端，且 new 只与 delete 配对。

两种表示都提供析构/容器清理和安全的重复初始化，不允许复制或移动。正常入队、出队、读取为 O(1)，clear 释放现有元素，为 O(n)；测试专用 invariant() 为线性扫描。

代码实现 #

顺序数组 #

利用循环数组实现.

#pragma once
#include <optional>
#include <stdexcept>
#include <vector>

template<class T>
class ArrayDQueue {
    std::vector<std::optional<T>> q_;
    std::size_t head_ = 0, size_ = 0;
public:
    ArrayDQueue() = default;
    ArrayDQueue(const ArrayDQueue&) = delete;
    ArrayDQueue& operator=(const ArrayDQueue&) = delete;
    void init(int length) {
        if (length <= 0) throw std::invalid_argument("capacity must be positive");
        std::vector<std::optional<T>> fresh(static_cast<std::size_t>(length));
        q_.swap(fresh);
        head_ = size_ = 0;
    }
    bool isEmpty() const { return size_ == 0; }
    bool isFull() const { return size_ == q_.size(); }
    std::size_t size() const { return size_; }
    void clear() noexcept {
        while (!isEmpty()) {
            q_[head_].reset();
            head_ = (head_ + 1) % q_.size();
            --size_;
        }
        head_ = 0;
    }
    bool enqueueToRear(const T& value) {
        if (isFull()) return false;
        q_[(head_ + size_) % q_.size()].emplace(value);
        ++size_;
        return true;
    }
    bool enqueueToFront(const T& value) {
        if (isFull()) return false;
        const auto next_head = (head_ + q_.size() - 1) % q_.size();
        q_[next_head].emplace(value);
        head_ = next_head;
        ++size_;
        return true;
    }
    std::optional<T> dequeueFromFront() {
        if (isEmpty()) return std::nullopt;
        auto result = q_[head_];
        q_[head_].reset();
        --size_;
        head_ = size_ ? (head_ + 1) % q_.size() : 0;
        return result;
    }
    std::optional<T> dequeueFromRear() {
        if (isEmpty()) return std::nullopt;
        const auto tail = (head_ + size_ - 1) % q_.size();
        auto result = q_[tail];
        q_[tail].reset();
        if (--size_ == 0) head_ = 0;
        return result;
    }
    std::optional<T> getFront() const {
        return isEmpty() ? std::nullopt : q_[head_];
    }
    std::optional<T> getRear() const {
        return isEmpty() ? std::nullopt : q_[(head_ + size_ - 1) % q_.size()];
    }
    bool invariant() const {
        if (size_ > q_.size()) return false;
        if (q_.empty()) return head_ == 0 && size_ == 0;
        if (head_ >= q_.size() || (!size_ && head_ != 0)) return false;
        std::size_t occupied = 0;
        for (const auto& item : q_) occupied += item.has_value();
        if (occupied != size_) return false;
        for (std::size_t i = 0; i < size_; ++i)
            if (!q_[(head_ + i) % q_.size()]) return false;
        return true;
    }
};

双向链表 #

#pragma once
#include <optional>
#include <stdexcept>

template<class T>
class LinkedDQueue {
    struct Point { T val; Point* next; Point* pre; };
    Point* head_ = nullptr;
    Point* tail_ = nullptr;
    int size_ = 0, limit_ = 0;
public:
    LinkedDQueue() = default;
    LinkedDQueue(const LinkedDQueue&) = delete;
    LinkedDQueue& operator=(const LinkedDQueue&) = delete;
    ~LinkedDQueue() { clear(); }
    void init(int length) {
        if (length <= 0) throw std::invalid_argument("capacity must be positive");
        clear();
        limit_ = length;
    }
    bool isEmpty() const { return size_ == 0; }
    bool isFull() const { return size_ == limit_; }
    int size() const { return size_; }
    void clear() noexcept {
        while (head_) {
            Point* old = head_;
            head_ = head_->next;
            delete old;
        }
        tail_ = nullptr;
        size_ = 0;
    }
    bool enqueueToRear(const T& value) {
        if (isFull()) return false;
        Point* fresh = new Point{value, nullptr, tail_};
        if (tail_) tail_->next = fresh;
        else head_ = fresh;
        tail_ = fresh;
        ++size_;
        return true;
    }
    bool enqueueToFront(const T& value) {
        if (isFull()) return false;
        Point* fresh = new Point{value, head_, nullptr};
        if (head_) head_->pre = fresh;
        else tail_ = fresh;
        head_ = fresh;
        ++size_;
        return true;
    }
    std::optional<T> dequeueFromFront() {
        if (isEmpty()) return std::nullopt;
        std::optional<T> result(head_->val);
        Point* old = head_;
        head_ = old->next;
        if (head_) head_->pre = nullptr;
        else tail_ = nullptr;
        --size_;
        delete old;
        return result;
    }
    std::optional<T> dequeueFromRear() {
        if (isEmpty()) return std::nullopt;
        std::optional<T> result(tail_->val);
        Point* old = tail_;
        tail_ = old->pre;
        if (tail_) tail_->next = nullptr;
        else head_ = nullptr;
        --size_;
        delete old;
        return result;
    }
    std::optional<T> getFront() const {
        if (!head_) return std::nullopt;
        return head_->val;
    }
    std::optional<T> getRear() const {
        if (!tail_) return std::nullopt;
        return tail_->val;
    }
    bool invariant() const {
        if (size_ < 0 || size_ > limit_) return false;
        if (!size_) return !head_ && !tail_;
        if (!head_ || !tail_ || head_->pre || tail_->next) return false;
        int count = 0;
        Point* previous = nullptr;
        for (Point* q = head_; q; q = q->next) {
            if (count++ >= size_ || q->pre != previous) return false;
            previous = q;
        }
        if (count != size_ || previous != tail_) return false;
        count = 0;
        Point* next = nullptr;
        for (Point* q = tail_; q; q = q->pre) {
            if (count++ >= size_ || q->next != next) return false;
            next = q;
        }
        return count == size_ && next == head_;
    }
};

滑动窗口问题 #

问题分析 #

输出每个长度为 k 的窗口的最小值和最大值，要求 1 <= k <= n。窗口不存在或 k 非法时明确拒绝，不访问空队首。

第一遍求最小值：队列从首到尾的值严格递增，插入前弹出队尾所有大于等于新值的元素。第二遍求最大值：队列从首到尾严格递减，弹出所有小于等于新值的队尾元素。相等时保留更靠后的下标，因为它失效更晚。

两遍都先从队首移除已离开窗口的下标，再维护单调性和入队。每个下标至多入队、出队各一次，故总时间 O(n)，队列空间 O(k)。

可以在 DQueue 中存储“值与位置”的结构体，也可以只存下标再访问原数组；下面采用后一种方式，并用同一算法分别测试数组、链式两种队列。

代码实现 #

下面的窗口函数使用前述队列操作，通过 optional 检查空值。原练习关联洛谷 P1886，具体提交版本和评测文件未附，本文不声称复现该次提交。输入输出由文末共用应用驱动提供。

template<template<class> class Queue = ArrayDQueue>
std::pair<std::vector<int>, std::vector<int>> sliding_minmax(
    const std::vector<int>& a, int k) {
    if (k <= 0 || static_cast<std::size_t>(k) > a.size())
        throw std::invalid_argument("window must satisfy 1 <= k <= n");
    const auto width = static_cast<std::size_t>(k);
    Queue<std::size_t> q;
    q.init(k);
    std::pair<std::vector<int>, std::vector<int>> result;
    for (int pass = 0; pass < 2; ++pass) {
        auto& output = pass == 0 ? result.first : result.second;
        for (std::size_t i = 0; i < a.size(); ++i) {
            while (!q.isEmpty() && i >= width && *q.getFront() <= i - width)
                q.dequeueFromFront();
            while (!q.isEmpty() && (pass == 0 ? a[*q.getRear()] >= a[i]
                                                             : a[*q.getRear()] <= a[i]))
                q.dequeueFromRear();
            if (!q.enqueueToRear(i)) throw std::logic_error("window queue full");
            if (i + 1 >= width) output.push_back(a[*q.getFront()]);
        }
        q.clear();
    }
    return result;
}

任务 3: 栈 #

快排非递归转化 #

问题分析 #

要进行非递归转化, 我们需要关注快速排序在递归过程中哪些值被传递到了下一层.

发现, 快速排序实际上只用传输区间端点 $l,r$ 这两个值, 所以我们可以利用栈, 每一层就存放这两个值, 然后在处理完当层之后, 将下一层递归的区间加入栈即可.

下面明确使用闭区间 [l,r]；空数组和单元素直接返回，只压入至少两个元素的区间。随机轴来自局部 std::mt19937，默认 seed 为 20260911。分区结果左侧严格小于轴，右侧大于等于轴；相等值很多时仍可能出现二次时间，不把随机轴说成最坏线性保证。

代码实现 #

inline std::size_t partition(std::vector<int>& a, std::size_t l,
                             std::size_t r, std::mt19937& rng) {
    if (l > r || r >= a.size()) throw std::out_of_range("invalid partition range");
    if (l == r) return l;
    std::uniform_int_distribution<std::size_t> pick(l, r);
    std::swap(a[pick(rng)], a[r]);
    const int pivot = a[r];
    std::size_t i = l;
    for (std::size_t j = l; j < r; ++j)
        if (a[j] < pivot) std::swap(a[i++], a[j]);
    std::swap(a[i], a[r]);
    return i;
}

inline void Quicksort(std::vector<int>& a, std::uint32_t seed = 20260911) {
    if (a.size() < 2) return;
    std::mt19937 rng(seed);
    std::vector<std::pair<std::size_t, std::size_t>> stack{{0, a.size() - 1}};
    while (!stack.empty()) {
        const auto [l, r] = stack.back();
        stack.pop_back();
        if (l >= r) continue;
        const auto p = partition(a, l, r, rng);
        if (p > l && p - l > 1) stack.push_back({l, p - 1});
        if (r > p && r - p > 1) stack.push_back({p + 1, r});
    }
}

算术混合运算表达式计算 #

问题分析及算法设计 #

使用运算符栈与数值栈，在中缀扫描时直接求值，不必先生成完整后缀表达式。以下是实数浮点参考计算器的明确语法，不声称复原了洛谷 P10473 的评测规则。

支持十进制整数、小数（含 .5、1.）、空白、圆括号、二元 + - * / ^ 及一元正负号；^ 在此表示乘方，不是 C++ 的按位异或。不支持科学计数法、隐式乘法、函数和变量。
优先级由高到低是乘方、一元正负号、乘除、加减。^ 右结合，故 2^3^2 = 512；一元符号作用于其后的表达式，-2^2 = -4，(-2)^2 = 4。
读到二元运算符时，弹出优先级更高的栈顶；优先级相等时，仅当当前运算符左结合才弹出。2+3*4 = 14，2*3+4 = 10。
用“当前位置是否需要操作数”区分一元与二元符号。读到一元号只入栈，不抢先归约前面的幂，因此 2*-3、2^-3 和连续符号不会导致数值栈下溢；不再用补 0 冒充一元负号。
括号是归约边界；每次弹栈都检查操作数个数，最后必须只剩一个数值。非法字符、空表达式、缺数、邻接数值与括号不匹配均返回带位置的错误结果。
除数为零、负底数的非整数次幂、0 的非正次幂和非有限结果被拒绝。本文将 0^0 记为定义域错误。输入长度上限 200000 字节，使用动态栈且不递归；结果是双精度近似值，不是符号计算或高精度数值库。

EvalResult 明确区分成功与错误，position 为 0 基字节位置；驱动显示时转换成从 1 开始的列号。语法和边界判断不依赖未提供的 I/O 模板。

代码实现 #

#pragma once
#include <charconv>
#include <cctype>
#include <cmath>
#include <string>
#include <system_error>
#include <vector>

struct EvalResult {
    bool ok;
    double value;
    std::string error;
    std::size_t position;
};

inline EvalResult evaluate(const std::string& input) {
    const auto fail = [](const char* code, std::size_t at) {
        return EvalResult{false, 0.0, code, at};
    };
    if (input.size() > 200000) return fail("input_too_long", 200000);
    struct Operator { char symbol; std::size_t position; };
    std::vector<double> values;
    std::vector<Operator> operators;
    const auto priority = [](char op) {
        if (op == '^') return 4;
        if (op == 'P' || op == 'N') return 3;
        if (op == '*' || op == '/') return 2;
        if (op == '+' || op == '-') return 1;
        return 0;
    };
    EvalResult error{true, 0.0, "", 0};
    const auto reduce = [&]() -> bool {
        if (operators.empty()) { error = fail("missing_operator", input.size()); return false; }
        const auto op = operators.back();
        const bool unary = op.symbol == 'P' || op.symbol == 'N';
        if (values.size() < (unary ? 1U : 2U)) {
            error = fail("missing_operand", op.position);
            return false;
        }
        double result = 0.0;
        const double right = values.back();
        if (unary) result = op.symbol == 'N' ? -right : right;
        else {
            const double left = values[values.size() - 2];
            switch (op.symbol) {
                case '+': result = left + right; break;
                case '-': result = left - right; break;
                case '*': result = left * right; break;
                case '/':
                    if (right == 0) { error = fail("division_by_zero", op.position); return false; }
                    result = left / right;
                    break;
                case '^':
                    if ((left == 0 && right <= 0) ||
                        (left < 0 && std::trunc(right) != right)) {
                        error = fail("power_domain", op.position);
                        return false;
                    }
                    result = std::pow(left, right);
                    break;
                default: error = fail("invalid_operator", op.position); return false;
            }
        }
        if (!std::isfinite(result)) { error = fail("numeric_overflow", op.position); return false; }
        operators.pop_back();
        values.pop_back();
        if (!unary) values.pop_back();
        values.push_back(result);
        return true;
    };
    bool need_operand = true;
    for (std::size_t i = 0; i < input.size();) {
        const char c = input[i];
        if (std::isspace(static_cast<unsigned char>(c))) { ++i; continue; }
        if ((c >= '0' && c <= '9') || c == '.') {
            if (!need_operand) return fail("missing_operator", i);
            const auto begin = i;
            bool digit = false;
            while (i < input.size() && input[i] >= '0' && input[i] <= '9') { digit = true; ++i; }
            if (i < input.size() && input[i] == '.') {
                ++i;
                while (i < input.size() && input[i] >= '0' && input[i] <= '9') { digit = true; ++i; }
            }
            if (!digit) return fail("invalid_number", begin);
            double value = 0;
            const auto parsed = std::from_chars(input.data() + begin, input.data() + i,
                                                value, std::chars_format::fixed);
            if (parsed.ec != std::errc{} || parsed.ptr != input.data() + i || !std::isfinite(value))
                return fail("invalid_number", begin);
            values.push_back(value);
            need_operand = false;
            continue;
        }
        if (c == '(') {
            if (!need_operand) return fail("missing_operator", i);
            operators.push_back({c, i++});
            continue;
        }
        if (c == ')') {
            if (need_operand) return fail("missing_operand", i);
            while (!operators.empty() && operators.back().symbol != '(')
                if (!reduce()) return error;
            if (operators.empty()) return fail("missing_left_parenthesis", i);
            operators.pop_back();
            ++i;
            continue;
        }
        if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^') {
            if (need_operand) {
                if (c != '+' && c != '-') return fail("missing_operand", i);
                // A prefix sign must not reduce a pending power: 2^-3 is valid.
                operators.push_back({c == '+' ? 'P' : 'N', i++});
                continue;
            }
            while (!operators.empty() && operators.back().symbol != '(' &&
                (priority(operators.back().symbol) > priority(c) ||
                 (priority(operators.back().symbol) == priority(c) && c != '^')))
                if (!reduce()) return error;
            operators.push_back({c, i++});
            need_operand = true;
            continue;
        }
        return fail("invalid_character", i);
    }
    if (need_operand) return fail("missing_operand", input.size());
    while (!operators.empty()) {
        if (operators.back().symbol == '(')
            return fail("missing_right_parenthesis", operators.back().position);
        if (!reduce()) return error;
    }
    if (values.size() != 1) return fail("missing_operator", input.size());
    return {true, values.back(), "", 0};
}

原练习记录关联洛谷 P10473，具体提交版本未附。以下保留其七组输入，并以本文的参考契约重新核对；这些样例不替代完整边界和内存测试。

输入	输出或错误
`2^10-1000-(5^3)+(3^2)`	`-92.000000`
`1-2+3-4+5-6`	`-3.000000`
`-(1-2^3)^(-2)+1`	`0.979592`
`2^3*2/4^2`	`1.000000`
`2(1+2^2)/(32-3)(1^10+2)-32`	`4.000000`
`((1+2)`	缺少右括号：`missing_right_parenthesis`
`1+2)`	缺少左括号：`missing_left_parenthesis`

上表保留原有七个输入，纠正最后两项写反的括号说明。还覆盖 2^3^2、2^-3、2*-3、小数、空串、除零和超长输入，测试源与运行方法见附件。

股票走势 #

这里求的是跨度而非前驱下标：若左侧最近一个严格更大值的位置为 j，则 1 基下标下 s_i=i-j；若不存在，则 s_i=i。相等值需要弹出，例如 2 2 2 2 的跨度为 1 2 3 4。

朴实的设计思想 #

我们直接枚举一个右端点 $i$ , 然后从 $i$ 开始往左枚举 $j$ , 直到遇到第一个比当前值大的位置. 时间复杂度 $\t O(n^2)$ .

利用栈 #

考虑维护一个单调栈, 此处我们需要找到左边第一个比自己大的位置, 那么就从左向右维护一个单调递减的单调栈.

具体过程就是, 从左至右遍历数组, 如果当前值大于等于栈顶, 就将栈顶弹出, 重复此过程. 那么栈顶元素就是左边最近的比当前值大的元素. 如果栈是空的, 就说明当前值左边没有比它大的, 即 $s_i = i$ (当下标从 $1$ 开始). 在弹出之后, 将当前值入栈.

利用数学归纳法的思想不难证明, 按照上述操作维护的栈是单调的.

时间复杂度 $\t O(n)$ .

具体代码如下.

inline std::vector<std::size_t> stock_spans(const std::vector<int>& a) {
    std::vector<std::size_t> stack, spans;
    for (std::size_t i = 0; i < a.size(); ++i) {
        while (!stack.empty() && a[stack.back()] <= a[i]) stack.pop_back();
        spans.push_back(stack.empty() ? i + 1 : i - stack.back());
        stack.push_back(i);
    }
    return spans;
}

任务 4: 基数排序 #

设计分析 #

LSD 基数排序从最低位到最高位分组；每一趟必须稳定，才能保留先前已排好的低位顺序。整数按数位依次进入 0 到 9 的十个 FIFO 队列，再按桶编号拼接。

归纳看，第 j 趟结束后，序列按最低 j 位有序；第 j+1 趟按更高位稳定分组，所以高位相等时仍保留低位顺序。处理最高位后得到整体次序。

原练习提到 radixSort1.txt 和字符串字符桶，但没有完整输入说明。下面明确两种参考范围：非负 uint64_t 整数，以及恰好 8 个 ASCII 英文字母的字符串。它们不是对原评测规格的断言；负整数、变长文本、Unicode 排序均不在这里偷偷扩展。

对于仅含 a 到 z 的等长字符串，可以用 26 个桶；下面为同时处理大小写，使用 128 个 ASCII 编号桶，其中字母实际占 52 个编号，按 ASCII 次序排列，大写在小写之前。

复杂度分析 #

整数可看成补齐前导 0 的数位串。令 m 为最大位数、n 为元素个数、b 为桶数，稳定分桶时间为 O(m(n+b))；桶数固定时写作 O(mn)。分桶需 O(n+b) 个存储位置，字符串实现还复制固定长度的字符串。

代码实现 #

整数 #

函数接收非负 uint64_t。驱动先拒绝负号和超出范围的输入，不能把负数静默转成巨大无符号数。最大值控制位数，每次乘 10 前确认还有更高位，避免位权溢出，也不因某一中间位恰好全为 0 而过早结束。

inline void radix_sort_nonnegative(std::vector<std::uint64_t>& a) {
    if (a.empty()) return;
    const auto maximum = *std::max_element(a.begin(), a.end());
    std::array<std::queue<std::uint64_t>, 10> buckets;
    for (std::uint64_t place = 1;;) {
        for (const auto value : a) buckets[(value / place) % 10].push(value);
        std::size_t i = 0;
        for (auto& bucket : buckets) {
            while (!bucket.empty()) {
                a[i++] = bucket.front();
                bucket.pop();
            }
        }
        if (maximum / place < 10) break;
        place *= 10; // The preceding test proves place <= maximum / 10.
    }
}

字符串 #

本参考实现保留 8 位、ASCII 字母的范围，并在任何下标访问前验证全部输入。短串、长串、非字母字节全部拒绝，不用越界读取来补齐字符。桶下标转为 unsigned char，与有符号 char 无关。

inline void radix_sort_ascii8(std::vector<std::string>& a) {
    for (const auto& s : a) {
        if (s.size() != 8) throw std::invalid_argument("expected eight ASCII letters");
        for (const unsigned char c : s)
            if (!((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')))
                throw std::invalid_argument("expected eight ASCII letters");
    }
    std::array<std::queue<std::string>, 128> buckets;
    for (int p = 7; p >= 0; --p) {
        for (const auto& s : a) buckets[static_cast<unsigned char>(s[p])].push(s);
        std::size_t i = 0;
        for (auto& bucket : buckets) {
            while (!bucket.empty()) {
                a[i++] = bucket.front();
                bucket.pop();
            }
        }
    }
}

编译、输入输出与复核 #

全部源码与测试使用 C++17 标准库，不依赖 read/write/flushout、未定义的随机函数或隐含全局数组。复核脚本会在指定的新目录编译三个程序，保留每条命令的输出与 JSON 结果，不安装软件。

g++ -std=c++17 -O1 -g -Wall -Wextra -Wpedantic -Werror tests.cpp -o tests
g++ -std=c++17 -O1 list_demo.cpp -o list_demo
g++ -std=c++17 -O1 applications_demo.cpp -o applications_demo
./tests
./list_demo single < list_testcase.txt > single-output.txt
./applications_demo radix-int < radixSort1.txt

这里的输入文件须由读者提供；原实验下发的两份文件尚未找回。也可直接用本页和附件内的输入示例测试。

模式	标准输入	标准输出
`list_demo array/single/double`	每行一串字符操作	每个合法行结束后的元素和状态；错误写入 stderr
`applications_demo window`	`n k`，接着 `n` 个 int	第一行窗口最小值，第二行最大值
`applications_demo quick`	`n`，接着 `n` 个 int	排序后的序列；空序列输出空行
`applications_demo stock`	`n`，接着 `n` 个 int	各位置的跨度
`applications_demo expr`	每行一个表达式	成功时固定 6 位小数；失败时 stderr 给错误及列号
`applications_demo radix-int`	直到 EOF 的非负 uint64_t，以空白分隔	稳定升序结果
`applications_demo radix-string`	直到 EOF 的 8 字母 ASCII 串，以空白分隔	ASCII 字典序结果

驱动的计数型输入明确限制 0 <= n <= 200000，校验缺值、额外值、无效数值和数值范围。程序返回 0 表示该次运行成功，2 表示输入或操作失败。非递归快排仍有 O(n²) 最坏情况，附件不是面向不可信网络输入的在线服务。

应用驱动如下；它把每个任务的实际结果输出出来，不再只把数据放到未声明的 res 数组中。

#include "applications.hpp"
#include "expression.hpp"
#include <charconv>
#include <iomanip>
#include <iostream>

template<class T>
T read_integer(std::istream& input) {
    std::string token;
    if (!(input >> token)) throw std::invalid_argument("missing integer");
    T value{};
    const auto parsed = std::from_chars(token.data(), token.data() + token.size(), value);
    if (parsed.ec != std::errc{} || parsed.ptr != token.data() + token.size())
        throw std::invalid_argument("invalid or out-of-range integer");
    return value;
}

template<class T>
void print_values(const std::vector<T>& values) {
    for (std::size_t i = 0; i < values.size(); ++i) {
        if (i) std::cout << ' ';
        std::cout << values[i];
    }
    std::cout << '\n';
}

int main(int argc, char** argv) {
    try {
        if (argc != 2) throw std::invalid_argument("usage: applications_demo window|quick|stock|expr|radix-int|radix-string");
        const std::string mode = argv[1];
        if (mode == "expr") {
            std::string line;
            bool failed = false, seen = false;
            while (std::getline(std::cin, line)) {
                seen = true;
                const auto result = evaluate(line);
                if (result.ok) std::cout << std::fixed << std::setprecision(6) << result.value << '\n';
                else {
                    std::cerr << result.error << " at column " << result.position + 1 << '\n';
                    failed = true;
                }
            }
            if (!seen || std::cin.bad()) throw std::invalid_argument("missing expression or read failure");
            return failed ? 2 : 0;
        }
        if (mode == "radix-int") {
            std::vector<std::uint64_t> values;
            while (std::cin >> std::ws && std::cin.peek() != EOF)
                values.push_back(read_integer<std::uint64_t>(std::cin));
            radix_sort_nonnegative(values);
            print_values(values);
        } else if (mode == "radix-string") {
            std::vector<std::string> values;
            for (std::string s; std::cin >> s;) values.push_back(s);
            radix_sort_ascii8(values);
            print_values(values);
        } else if (mode == "window" || mode == "quick" || mode == "stock") {
            const int n = read_integer<int>(std::cin);
            if (n < 0 || n > 200000) throw std::invalid_argument("n must be between 0 and 200000");
            const int k = mode == "window" ? read_integer<int>(std::cin) : 0;
            std::vector<int> values(static_cast<std::size_t>(n));
            for (auto& value : values) value = read_integer<int>(std::cin);
            std::string extra;
            if (std::cin >> extra) throw std::invalid_argument("unexpected extra token");
            if (mode == "quick") { Quicksort(values); print_values(values); }
            else if (mode == "stock") print_values(stock_spans(values));
            else {
                const auto [minimum, maximum] = sliding_minmax(values, k);
                print_values(minimum);
                print_values(maximum);
            }
        } else throw std::invalid_argument("unknown mode");
        if (std::cin.bad()) throw std::runtime_error("input read failed");
        return 0;
    } catch (const std::exception& e) {
        std::cerr << "error: " << e.what() << '\n';
        return 2;
    }
}

本轮复核包括三种 List 的统一契约、两种队列与 std::deque 的随机差分、首尾交替删除/删空再用、容量与非法下标、重复初始化与生命周期、排序及窗口的独立对照，以及表达式边界与随机语法树。内存检查使用 ASan/UBSan；没有用“列举几个正确输出”替代检查，也没有把本轮结果说成原实验评测已通过。

实验 2: 线性表实现及应用 #

任务 1: 为指定的 List ADT 实现各种数据结构 #

操作契约与实现范围 #

代码实现 #

顺序数组 #

共用字符指令驱动 #

单向链表 #

双向链表 #

代码差异分析 #

不同存储方式复杂度分析 #

任务 2: 为指定的 DQueue ADT 实现两种数据结构 #

双端队列契约 #

代码实现 #

顺序数组 #

双向链表 #

滑动窗口问题 #

问题分析 #

代码实现 #

任务 3: 栈 #

快排非递归转化 #

问题分析 #

代码实现 #

算术混合运算表达式计算 #

问题分析及算法设计 #

代码实现 #

股票走势 #

朴实的设计思想 #

利用栈 #

任务 4: 基数排序 #

设计分析 #

复杂度分析 #

代码实现 #

整数 #

字符串 #

编译、输入输出与复核 #

评论