实验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_;
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：
1
2
| 35 12 10 8 7 3
Array size = 6
|
输入样例2：
输出样例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
|
bool DecrSeqInsert(ArrNode& array, int x) {
if (array.size_ == kMaxSize) {
return false;
}
for (int i = 0; i < array.size_; ++i) {
if (array.data_[i] == x) {
return false;
}
}
int i;
for (i = 0; i < array.size_; i++) {
if (array.data_[i] < x) {
break;
}
}
for (int j = array.size_-1; j >= i; j--) {
array.data_[j+1] = array.data_[j];
}
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_;
int size_;
explicit ArrNode(int n) : size_(0), data_(vector<int>(n)) {}
};
bool DecrSeqInsert(ArrNode& array, int x) {
if (array.size_ == kMaxSize) {
return false;
}
for (int i = 0; i < array.size_; ++i) {
if (array.data_[i] == x) {
return false;
}
}
int i;
for (i = 0; i < array.size_; i++) {
if (array.data_[i] < x) {
break;
}
}
for (int j = array.size_-1; j >= i; j--) {
array.data_[j+1] = array.data_[j];
}
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.易错：
如果这样写会有个错误：
bool DecrSeqInsert(ArrNode& array, int x) {
if (array.size_ == kMaxSize) {
return false;
}
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) {
for (int j = array.size_-1; j > i; j--) {
array.data_[j+1] = array.data_[j];
}
array.data_[i + 1] = x;
array.size_++;
return true;
}
}
}
<!--code9-->
情况 1：构造函数有explicit（你的代码当前状态）
1
2
3
4
5
6
|
ArrNode array(kMaxSize);
printArray(array);
printArray(kMaxSize);
|
这时候编译器会报错，因为explicit禁止了 “整数→ArrNode” 的隐式转换，你必须明确传递ArrNode对象。
情况 2：如果去掉explicit
1
2
|
ArrNode(int n) : size_(0), data_(vector<int>(n)) {}
|
这时再调用printArray(kMaxSize)，编译器会自动做一件事：
- 用
kMaxSize作为参数，隐式创建一个临时ArrNode对象（相当于ArrNode(kMaxSize)）
- 把这个临时对象传给
printArray函数
这就导致了 “意外转换”：你本来想传一个整数，结果编译器偷偷帮你创建了一个ArrNode对象，而这很可能不符合你的意图。
总结：
explicit 只用于修饰单个参数的构造函数（或除第一个参数外其余参数都有默认值的构造函数）。- 你的
ArrNode 是一个管理数组的类，它的构造函数需要一个 int 参数（n）来指定内部 vector 的初始容量。加上 explicit 可以：
- 避免有人误写
ArrNode array = kMaxSize; 这种不直观的代码
- 防止在函数传参时，把
int 类型的 kMaxSize 或其他整数意外转换为 ArrNode 对象
- 让代码意图更清晰：创建
ArrNode 对象必须明确调用构造函数，而不是通过隐式转换
