一维数组¶

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

一维数组的定义

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

例如，
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};
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 位开始存。

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

下标访问越界

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

int a[10];
有效下标范围是[0, 9]
a[-1]、a[10]，这种就是错误的访问

// 在DEV C++中，编译不会报错，但运行会出现问题

数组的遍历¶

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

从左向右遍历

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	字符数组

最值问题¶

求最大值、最小值，依然是用 "打擂台" 的方式进行。

int a[110], n, maxn = -1, minn = 2e9;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        maxn = max(maxn, a[i]);
        minn = min(minn, a[i]);
    }

    cout << maxn << ' ' << minn;

    return 0;
}

标记数组¶

标记数组，用于维护元素的状态（是否出现过、是否访问过、是否处理过）。

bool vis[110];

整数去重

bool vis[5010]; // vis[i]表示 i 这个数值是否出现过，vis数组的大小取决于值域
int n, x;

int main() {
    cin >> n;
    while (n--){
        cin >> x;
        if (!vis[x]){
            cout << x << ' ';
            vis[x] = true;
        }
    }

    return 0;
}

计数数组¶

计数数组，用于统计元素出现的次数，统计这个编号的位置存了多少东西。

int cnt[110]; // cnt[i] 表示 i 这个数值出现了几次，中括号里放的是值域，而不是元素的个数

有 n 个数，值域范围是 0 - 9，输出 0 - 9 这 10 个数字，每个数字出现多少次

int cnt[15], n, x;

int main() {
    cin >> n;
    while (n--) {
        cin >> x;
        cnt[x]++;
    }

    for (int i = 0; i < 10; i++) cout << cnt[i] << ' ';

    return 0;
}

有 n 个储蓄罐，编号 0 ~ n-1，第 i 天挑选一个储蓄罐 x，存入 i 元

m 天后，输出每个储蓄罐里的钱数

int cnt[1010], n, m, x; // cnt[i] 表示第 i 个储蓄罐有多少钱

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m, i++) {
        cin >> x;
        cnt[x] += i;
    }

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

    return 0;
}

筛选元素存储¶

输入 n 个数，并非把 n 个数都存起来，而是把满足条件的数存起来。

具体有多少个数要存？要看实际有多少个满足条件的数。

输入 n 个数，将其中的奇数存起来，放到一个新的数组里，并依次输出

int a[110], n, idx, x;

int main() {
    cin >> n;
    while (n--) {
        cin >> x;
        if (x % 2) a[idx++] = x;
    }

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

    return 0;
}

短除法转进制，输入一个十进制数 n，转成二进制（将余数存到数组中）

int a[110], n, idx;

int main() {
    cin >> n;
    while (n) {
        a[idx++] = n % 2;
        n /= 2;
    }

    for (int i = idx - 1; i >= 0; i--) cout << a[i]; // 从后向前输出

    return 0;
}

存储月份¶

月份大小的口诀是：“一三五七八十腊，三十一天永不差；四六九冬三十日，唯有二月二十八”。

但在写程序时，要写很多个 if，那是很烦的。

我们可以用数组将每个月份对应的天数存起来，和下标对应上，这样就可以通过下标访问，快速得到月份天数。

int a[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// 如果不用数组预先存储起来，就需要用if进行判断
if (m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 || m == 12) cout << 31;
else if (m == 4 || m == 6 || m == 9 || m == 11) cout << 31;
else cout << 28;

相同的，我们在进行十进制转十六进制的时候，会遇到 ABCDEF 的情况，那要写很多 if 语句，很是麻烦。

于是，我们可以把数字和字符的转化关系，存到一个数组里，方便使用。

string s = "0123456789ABCDEF";

cout << s[10];  // 就会得到一个大A

我们到目前为止，还没有学习到 string 是什么。

不妨往前翻一翻，看一下 string 的基本定义，就能理解这里了。

数组上的移动¶

我们可以用数组表示过河时，河中间的一排石头，模拟跳石头过河的过程。

这个过程，就是数组上的移动、跳跃、按一定规则选择元素的过程。

河中有 n 个石头，排成一列指向对岸，小青蛙最长跳跃距离是 k

问，小青蛙最多可以跳到第几个石头上

int a[110], n, k;

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

    for (int i = 1; i <= n; i++)
        if (a[i] - a[i - 1] > k) {
            cout << i - 1;
            return 0;
        }

    cout << n; // 可以跳到最后一个石头

    return 0;
}

用常量开数组¶

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

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

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