一维¶

一维数组¶

一维数组用于存储一组相同类型的元素，这些元素在内存中是连续存储的，并可以通过下标进行访问和操作。

一维数组的定义

数据类型 数组名称[数组大小]

例如，
int a[110];  // 开了一个名字叫做小a的数组，存储110个int类型的变量

看题目的数据范围，

如果是100个数据，开100大小；

如果是1000个数据，开1010大小。

数组的初始化¶

数组开到全局变量，默认都是0

int a[110];

int main() {
    ...
}

将数组定义到 int main() 里，初始值默认是随机数。

在 Dev C++ 中，可能会让你感觉到都是 0，但提交 OJ，肯定出错。

举一个不好的写法

int main() {
    int n;
    cin >> n;
    int a[n];
}
// 这是最糟糕的写法，我们不要这样写代码
// 见到一个，要阻止一个

使用大括号，进行初始化

最重要的是，数组开到全局变量。

int a[] = {0, 1, 2, 3, 4};   // 省略数组长度，按照初始化列表的长度，数组长度为5
int a[10] = {0, 1, 2, 3, 4}; // 未赋值的元素，自动初始化为0

使用memset() 函数，进行初始化

int a[110];

int main() {
    memset(a, 0, sizeof a); // 初始化成0
    memset(a, 0x3f, sizeof a); // 初始化成极大值，都是0x3f3f3f3f
    memset(a, -1, sizeof a); // 初始化成-1
    ...
}

// 关于 memset() 这个函数的原理，需要掌握二进制之后，再回来理解

数组的输入输出¶

int a[110], n;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n; i++) cout << a[i] << ' ';

    return 0;
}

数组的访问(下标)¶

下标访问

数组名[下标]

例如，
a[0]，访问第0位
a[i]，访问第i位

数组的下标从 0 开始，我们存数据的时候，一般从第 0 位开始存（0-indexed）

当然，我们也可以从第 1位开始存，这样我们就需要整体偏移一下。

下标访问越界

不能访问不在数组存储空间范围内的元素。

int a[10];

// 有效下标范围是[0, 9]
// a[-1]、a[10]，这种就是错误的访问
// 数组越界，会导致不可预测的后果，发生运行时错误（runtime error）

数组的遍历¶

遍历，按特定顺序访问数据结构中所有元素的过程。

从左向右遍历

for (int i = 0; i < n; i++) cout << a[i] << ' ';

从右向左遍历

for (int i = n - 1; i >= 0; i--) cout << a[i] << ' ';

常用数组名称¶

数组名称	单词全拼	使用场景
`a[ ], arr[ ]`	array	最通用的数组名
`cnt[ ]`	count	计数数组
`dis[ ], d[ ]`	distance	距离、步数
`vis[ ], st[ ]`	visit, state	维护是否访问过
`s[ ]`	string	字符数组

用常量开数组¶

当我们需要开多个数组的时候，需要写很多个 0，很容易多写一个少写一个 0。

为了避免这种低级错误，我们可以使用常量的方式开数组。

const int N = 1e5 + 10;
int a[N], b[N];