实验1-1 有序数组的插入（C++版）

分数 20

作者刘凯源

单位华东师范大学

给定存储了n个从大到小排好序的整数，试将任一给定整数 x 插入数组中合适的位置，以保持结果依然有序。分析算法在最坏、最好情况下的时间、空间复杂度。具体来说，不妨假设整数序列存储为一个序列 array，这个序列的结构定义在下面给出，数据存放在数组 data 中。因为数组长度是有限的，我们在此假设 data 数组的最大长度为 kMaxSize。如果在执行插入之前，数组已经满了，则插入失败，返回 false；如果待插入的元素 x 已经在data中，则不要重复插入，返回 false；如果插入成功，则返回 true。

函数接口定义：

bool DecrSeqInsert(ArrNode& array, int x);

其中ArrNode定义如下:

class ArrNode {
    public:
        vector<int> data_; // 使用vector来动态管理数组大小
        int size_;         // 数组的大小
        explicit ArrNode(int n) : size_(0), data_(vector<int>(n)) {}
};

这里题目保证传入的数据是递减有序的。

裁判测试程序样例：

int main() {
     int n, x;
    cin >> n;
    ArrNode array(kMaxSize);
    array.size_ = n;
    for (int i = 0; i < n; i++) {
        cin >> array.data_[i];
    }
    cin >> x;
    if (!DecrSeqInsert(array, x)) {
        cout << "Insertion failed." << endl;
    } 
    for (int i = 0; i < array.size_; i++) {
        if (i > 0) cout << " ";
        cout << array.data_[i];
    }
    cout << endl;
    cout << "Array size = " << array.size_ << endl;
    return 0;
}

输入样例1：

5
35 12 8 7 3
10

输出样例1：

35 12 10 8 7 3
Array size = 6

输入样例2：

6
35 12 10 8 7 3
8

输出样例2：

Insertion failed.
35 12 10 8 7 3
Array size = 6

解析

bool DecrSeqInsert(ArrNode& array, int x) {
    if (array.size_ >= kMaxSize)
    {
        return false;
    }
    if (array.size_ == 0)
    {
        array.data_[0] = x;
        array.size_++;
        return true;
    }
    for (int i = 0; i < array.size_; i++)
    {
        if (array.data_[i] == x)
        {
            return false;
        }
        else if (array.data_[i] > x && i == array.size_ - 1)
        {
            array.data_[array.size_] = x;
            array.size_++;
            return true;
        }
        else
        if (array.data_[i] < x)
        {
            for (int j = array.size_; j > i; j--)
            {
                array.data_[j] = array.data_[j - 1];
            }
            array.data_[i] = x;
            array.size_++;
            return true;
        }

    }
}

注意

长度为0的情况，此时如果进入循环：

for (int i = 0; i < array.size_; i++)

会是i = 0；i < 0 直接报错，所以要单独做一次判断

实验2-1 求链式线性表的倒数第 m 项（C++版）

分数 20

作者刘凯源

单位华东师范大学

请设计时间和空间上都尽可能高效的算法，求链式存储的线性表的倒数第m（>0）个元素。

函数接口定义：

template <typename ElemType>
ElemType LinkedList<ElemType>::Find(int m)

其中LinkedList结构定义如下

template <typename ElemType>
class LinkedList
{
    public:
    struct ListNode { // 单链表的结点类型
        ElemType data_; // 存储数据
        ListNode* next_; // 线性表中下一个元素的位置
    };
    using Position = ListNode*;  // 指针即结点位置
    struct ListException  // 异常处理
    {
        std::string error_;
        explicit ListException(std::string s) : error_(std::move(std::move(s))) {};
    };
    LinkedList();  // 构造函数，初始化一个空的线性表
    LinkedList(const LinkedList&);
    LinkedList& operator=(const LinkedList&);
    ~LinkedList();         // 析构函数,释放线性表占用的空间
    [[nodiscard]] int Length() const;  // 返回线性表中的元素个数，即表的长度
    ElemType Get(int i) const;  // 返回线性表中第i个元素的值
    void Insert(int i, ElemType x);  // 在线性表第i个位置上插入元素x
    void Remove(int i);              // 从线性表中删除第i个元素
    ElemType Find(int m);//求链式存储的线性表的倒数第m
    private:
    Position head_;  // 单链表头指针,指向空头结点
    int length_;     // 表长
};

函数接口定义中，ElemType是用户定义的数据类型，例如 int、double 或者 char 等。函数 Find 的功能是，返回带空头结点的单链表 list 的倒数第 m 个元素的值，并且不得对 list 做任何改变。如果这样的元素不存在，则返回一个错误标志 ERROR（这个标志的值由裁判程序定义）。

裁判测试程序样例：

int main()
{
    LinkedList<int> mylist;
    int n, d;
    std::cin >> n;
    try {
        for(int i=1; i<=n; i++)
        {
            std::cin >> d;
            mylist.Insert(i,d);
        }
    } catch(LinkedList<int>::ListException e) {
        std::cout << e.error_ <<std::endl;
    }
    int m;
    std::cin >> m;
    std::cout << mylist.Find(m) << std::endl;
    for (int i = 1; i <= mylist.Length(); i++)  {
        std::cout << mylist.Get(i) << (i == mylist.Length() ? '\n' : ' ');
    }
    return 0;
}

输入样例：

在这里给出一组输入。例如：

5
1 2 4 5 6
3

输出样例：

在这里给出相应的输出。例如：

4
1 2 4 5 6

解析

template <typename ElemType>
ElemType LinkedList<ElemType>::Find(int m) {
    // 1. 检查m的有效性
    if (m <= 0) {
        // 抛出异常：m必须大于0
        throw ListException("Error: m must be greater than 0.");
    }
    
    // 初始化快慢指针，都指向第一个数据节点
    ListNode* fast = head_->next_;
    ListNode* slow = head_->next_;

    // 2. 快指针先行 m-1 步
    // fast 先走 m-1 步，如果走到头了，说明链表长度 L < m
    for (int i = 0; i < m; ++i) {
        if (fast == nullptr) {
            // fast在移动 m 步前就遇到了 nullptr，说明 L < m。
            // 抛出异常：倒数第 m 个元素不存在
            throw ListException("Error: List length is less than m. Element does not exist.");
        }
        fast = fast->next_;
    }

    // 3. 快慢指针同步移动
    // 现在 fast 领先 slow m 个节点。
    // 当 fast 指向 nullptr 时 (走到链表尾的下一个)，slow 就指向倒数第 m 个节点。
    while (fast != nullptr) {
        slow = slow->next_;
        fast = fast->next_;
    }

    // 4. 返回结果
    // 由于 m <= L 已经在上面检查过，此时 slow 不会是 nullptr
    // 但为了代码的健壮性，我们可以再做一次检查（通常不是必须的）
    if (slow == nullptr) {
        // 理论上不会发生，除非链表在操作过程中被修改
        throw ListException("Internal Error: Unexpected null pointer.");
    }

    return slow->data_;
}

注意

I.

作者第一次代码

template <typename ElemType>
ElemType LinkedList<ElemType>::Find(int m)
{
    if (m < 1 || m > length_ || m == 0)
    {
        return -1;
    }
    Position p = head_->next_;
    Position q = head_->next_;
    for (int i = 1; i < m; i++)
    {
        p = p->next_;
    }
    while (p->next_ != nullptr)
    {
        p = p->next_;
        q = q->next_;
    }
    return q->data_;
}

会出现19分的情况。

经过豆包、deepseek的深度思考还是19分

豆包：

template <typename ElemType>
ElemType LinkedList<ElemType>::Find(int m) {
    // 处理 m 不合法或链表长度不足的情况
    if (m < 1 || m > length_) {
        return ERROR; // 确保 ERROR 在当前作用域可见
    }
    
    Position p = head_->next_; // 快指针，先移动 m-1 步
    Position q = head_->next_; // 慢指针，最终指向倒数第 m 项
    
    // 快指针先移动 m-1 步
    for (int i = 1; i < m; ++i) {
        p = p->next_;
    }
    
    // 快慢指针同时移动，直到快指针到达最后一个节点
    while (p->next_ != nullptr) {
        p = p->next_;
        q = q->next_;
    }
    
    return q->data_;
}

deepseek：

template <typename ElemType>
ElemType LinkedList<ElemType>::Find(int m)
{
    // 检查边界条件
    if (m < 1 || m > length_) {
        // 这里应该返回错误标志，但裁判程序没有定义ERROR
        // 根据测试用例，返回-1可能是可以的
        return -1;
    }
    
    Position p = head_->next_;
    Position q = head_->next_;
    
    // 先让p指针向前移动m-1步
    for (int i = 1; i < m; i++) {
        if (p == nullptr) {
            return -1; // 额外保护，虽然理论上不会发生
        }
        p = p->next_;
    }
    
    // 然后p和q同时移动，直到p到达最后一个节点
    while (p->next_ != nullptr) {
        p = p->next_;
        q = q->next_;
    }
    
    return q->data_;
}

最终是Gemini的普通思考给出了正确答案

II.

作者猜测，可能是因为系统要接受的是异常处理，如果把deepseek的

return -1;

改为

return ERROR;

又会报错为没有定义ERROR。

所以，只能使用ListException来做异常抛出，格式：

throw ListException("······")

对于struct ListException // 异常处理 { std::string error_; explicit ListException(std::string s) : error_(std::move(std::move(s))) {}; };详细解释

这段代码定义了一个自定义异常结构体 ListException，用于在链表操作（如查找、插入、删除等）出现错误时，传递具体的错误信息。下面详细拆解每一部分：

1. 结构体的本质与用途

struct ListException 是一个自定义异常类型（C++ 中 struct 和 class 主要区别是默认访问权限，这里用 struct 也能实现类的功能）。其核心作用是：当链表操作（如找倒数第 m 个元素、插入元素等）遇到非法情况（如 m 不合法、链表为空等）时，抛出包含错误描述的异常对象，让上层代码（如 main 函数）能捕获并处理错误，而非让程序直接崩溃。

2. 成员变量 `error_`

std::string error_;

作用：存储具体的错误描述文本（比如 "m必须大于0"、"链表长度不足" 等）。
类型：std::string 是 C++ 标准库的字符串类型，支持灵活的文本存储与操作。

3. 构造函数 `ListException(std::string s)`

explicit ListException(std::string s) : error_(std::move(std::move(s))) {};

explicit 关键字：防止「隐式类型转换」。例如，避免直接用 std::string 对象隐式转换成 ListException 类型，确保必须显式构造异常对象（增强代码安全性，避免意外的类型转换错误）。
参数 s：传入具体的错误描述字符串（如 "Error: m must be greater than 0."）。
成员初始化列表 error_(std::move(std::move(s)))：
- 这里的 std::move 是为了转移字符串的所有权，避免对 std::string 进行 “深拷贝”（减少内存开销，提高效率）。
- 注：代码中两次 std::move 是冗余的，实际写 error_(std::move(s)) 即可 —— 一次 std::move 就足以把 s 的资源转移给 error_，让 s 变为 “有效但未指定值” 的状态（不影响异常对象的创建，且性能更优）。

4. 异常的使用场景

当链表操作出现错误时，通过 throw 抛出 ListException 对象。例如，在 Find 函数中检测到 m <= 0 时：

if (m <= 0) {
    throw ListException("Error: m must be greater than 0.");
}

上层代码（如 main 函数）会用 try-catch 捕获异常，处理错误信息：

try {
    // 可能抛出 ListException 的链表操作（如 mylist.Find(m)）
} catch (LinkedList<int>::ListException& e) {
    std::cout << "错误发生：" << e.error_ << std::endl;
}

总结

ListException 的核心价值是将 “错误类型” 和 “错误描述” 封装成对象，通过 C++ 的异常机制实现 “错误处理与正常业务逻辑分离”，让代码更易维护（不同错误可通过不同的异常信息区分），也更安全（避免非法操作导致程序崩溃）。

实验1-1 有序数组的插入（C++版）

函数接口定义：

裁判测试程序样例：

输入样例1：

输出样例1：

输入样例2：

输出样例2：

解析

注意

实验2-1 求链式线性表的倒数第 m 项（C++版）

函数接口定义：

裁判测试程序样例：

输入样例：

输出样例：

解析

注意

I.

II.

对于struct ListException // 异常处理 { std::string error_; explicit ListException(std::string s) : error_(std::move(std::move(s))) {}; };详细解释

1. 结构体的本质与用途

2. 成员变量 error_

3. 构造函数 ListException(std::string s)

4. 异常的使用场景

总结

2. 成员变量 `error_`

3. 构造函数 `ListException(std::string s)`