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

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

分数 20

作者 刘凯源

单位 华东师范大学

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

函数接口定义：

1
bool DecrSeqInsert(ArrNode& array, int x);

其中ArrNode定义如下:

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

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

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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：

1
2
3
5
35 12 8 7 3
10

输出样例1：

1
2
35 12 10 8 7 3
Array size = 6

输入样例2：

1
2
3
6
35 12 10 8 7 3
8

输出样例2：

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

函数代码（题目要求提交的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 向递减递减序列（Decreasing Sequence）中插入元素
bool DecrSeqInsert(ArrNode& array, int x) {
    // 数组已经满了，则插入失败，返回 false
    if (array.size_ == kMaxSize) {
        return false;
    }
    // 避免重复插入
    for (int i = 0; i < array.size_; ++i) {
        if (array.data_[i] == x) {
            return false;
        }
    }
    //找到插入位置i
    int i; // 这里先定义插入位置i，方便后续把插入的x放入array.data_[i+1]中
    for (i = 0; i < array.size_; i++) {
        // 找到第一个比x小的元素
        if (array.data_[i] < x) {
            break;
        }
    }
    // 把比x小的元素往后挪
    for (int j = array.size_-1; j >= i; j--) {
        array.data_[j+1] = array.data_[j];
    }
    // 将x插入规定位置
    array.data_[i] = x;
    // 表长++
    array.size_++;
    return true;
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <vector>

using namespace std;

const int kMaxSize = 1000;

class ArrNode {
public:
    vector<int> data_; // 使用vector来动态管理数组大小
    int size_;         // 数组的大小
    explicit ArrNode(int n) : size_(0), data_(vector<int>(n)) {}
};
// 向递减递减序列（Decreasing Sequence）中插入元素
bool DecrSeqInsert(ArrNode& array, int x) {
    // 数组已经满了，则插入失败，返回 false
    if (array.size_ == kMaxSize) {
        return false;
    }
    // 避免重复插入
    for (int i = 0; i < array.size_; ++i) {
        if (array.data_[i] == x) {
            return false;
        }
    }
    //找到插入位置i
    int i; // 这里先定义插入位置i，方便后续把插入的x放入array.data_[i+1]中
    for (i = 0; i < array.size_; i++) {
        // 找到第一个比x小的元素
        if (array.data_[i] < x) {
            break;
        }
    }
    // 把比x小的元素往后挪
    for (int j = array.size_-1; j >= i; j--) {
        array.data_[j+1] = array.data_[j];
    }
    // 将x插入规定位置
    array.data_[i] = x;
    // 表长++
    array.size_++;
    return true;
}

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;
}

Summary

1.易错：

  • 如果这样写会有个错误：

  • // 向递减递减序列（Decreasing Sequence）中插入元素
bool DecrSeqInsert(ArrNode& array, int x) {
    // 数组已经满了，则插入失败，返回 false
    if (array.size_ == kMaxSize) {
        return false;
    }
    // 避免重复插入，并把符合条件的x插入
    for (int i = 0; i < array.size_; ++i) {
        if (array.data_[i] == x) {
            return false;
        } else if (array.data_[i] > x && array.data_[i + 1] < x) {
            // 把比x小的元素往后挪
            for (int j = array.size_-1; j > i; j--) {
                array.data_[j+1] = array.data_[j];
            }
            // 把x插到规定位置
            array.data_[i + 1] = x;
            // 插入了一个元素表长++
            array.size_++;
            return true;
        }
    }
}

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40

      | 测试点 | 提示               | 内存(KB) | 用时(ms) | 结果     | 得分  |      |
      | ------ | ------------------ | -------- | -------- | -------- | ----- | ---- |
      | 2      | 大数据，插入最大值 | 1324     | 46       | 答案错误 | 0 / 2 |      |

    - 如果插入的是最大值，代码没考虑到

    ### 2.explicit是啥

    `explicit` 是一个用于修饰类构造函数的关键字，它的核心作用是**禁止构造函数的隐式类型转换**，确保构造函数**只能被显式调用**。

    #### 具体作用：

    当一个类的构造函数只有**一个参数**时，C++ 编译器默认允许一种「隐式转换」—— 可以用该参数类型的值**直接**初始化对象，或者赋值给对象。而 `explicit` 会禁用这种转换，强制要求**必须显式**调用构造函数。

    #### 举例

    假设我们添加一个函数，参数是`ArrNode`类型：

    cpp



    运行









    ```cpp
    // 一个需要ArrNode对象作为参数的函数
    void printArray(ArrNode arr) {
        for (int i = 0; i < arr.size_; i++) {
            cout << arr.data_[i] << " ";
        }
    }

情况 1：构造函数有explicit（你的代码当前状态）

1
2
3
4
5
6
// 正确写法：显式创建ArrNode对象
ArrNode array(kMaxSize);
printArray(array);  // 正确

// 错误写法：试图直接传整数
printArray(kMaxSize);  // 编译报错！无法隐式转换

这时候编译器会报错，因为explicit禁止了 “整数→ArrNode” 的隐式转换，你必须明确传递ArrNode对象。

情况 2：如果去掉explicit

1
2
// 构造函数没有explicit修饰
ArrNode(int n) : size_(0), data_(vector<int>(n)) {}

这时再调用printArray(kMaxSize)，编译器会自动做一件事：

  1. 用kMaxSize作为参数，隐式创建一个临时ArrNode对象（相当于ArrNode(kMaxSize)）
  2. 把这个临时对象传给printArray函数

这就导致了 “意外转换”：你本来想传一个整数，结果编译器偷偷帮你创建了一个ArrNode对象，而这很可能不符合你的意图。

总结：

  • explicit 只用于修饰单个参数的构造函数（或除第一个参数外其余参数都有默认值的构造函数）。
  • 你的 ArrNode 是一个管理数组的类，它的构造函数需要一个 int 参数（n）来指定内部 vector 的初始容量。加上 explicit 可以：
  1. 避免有人误写 ArrNode array = kMaxSize; 这种不直观的代码
  2. 防止在函数传参时，把 int 类型的 kMaxSize 或其他整数意外转换为 ArrNode 对象
  3. 让代码意图更清晰：创建 ArrNode 对象必须明确调用构造函数，而不是通过隐式转换