程序 = 算法 + 数据结构，数组是存储数据的强而有力的手段。

数组是一组有序数据的集合，每一个元素都属于同一个数据类型。数组均由连续的存储单元组成，每个地址一一对应于数组的每一个元素。

1. 一维数组

1.1 数组的定义

数组的定义方式和变量类似。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a[10], b[10];
    float f[33];
    double d[123];
    char c[21];

    return 0;
}

1.2 数组的初始化

在main函数内部，未初始化的数组中的元素是随机的。

局部变量会定义在栈里边，全局变量会定义在堆里边 零页 申请完用的时候再开。

堆区在底层，栈区虚拟在上层，中层为静态存储区，总大小为内存大小。

c++栈空间 1 MB

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a[3] = {0, 1, 2};           // 含有3个元素的数组，元素分别是0, 1, 2
    int b[] = {0, 1, 1};            // 维度是3的数组
    int c[5] = {0, 1, 2};           // 等价于c[] = {0, 1, 2, 0, 0}
    char d[3] = {'a', 'b', 'c'};    // 字符数组的初始化
    float e[5] = {0};               // 将数组全部元素初始化为0 
    return 0;
}

1.3 访问数组元素

通过下标访问数组。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a[3] = {0, 1, 2};  // 数组下标从0开始

    cout << a[0] << ' ' << a[1] << ' ' << a[2] << endl;

    a[0] = 5;

    cout << a[0] << endl;

    return 0;
}

练习题1： 使用数组实现求斐波那契数列的第 N 项。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    int f[100];

    cin >> n;

    f[0] = 0, f[1] = 1;
    for (int i = 2; i <= n; i ++ ) f[i] = f[i - 1] + f[i - 2];

    cout << f[n] << endl;

    return 0;
}

练习题2：输入一个 n，再输入 n 个整数。将这 n 个整数逆序输出。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    int a[100];

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

    return 0;
}

练习题3：输入一个 n ，再输入 n 个整数。将这个数组顺时针旋转 k(k≤n) 次，最后将结果输出。旋转一次是指：将最右边的数放到最左边。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a[100];
    int n, k;
    cin >> n >> k;
    
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    
    while ( k -- )
    {
    	int t = a[n - 1];
    	for (int i = n - 2; i >= 0; i -- )
          a[i + 1] = a[i];
    	a[0] = t;
    }
    
    for(int i = 0; i < n; i ++ ) cout << a[i] << ' ';
 	
	return 0; 
}

reverse的范围是[start, end)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, k;
    int a[100];

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

    reverse(a, a + n);
    reverse(a, a + k);
    reverse(a + k, a + n);

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

    return 0;
}

练习题4：输入 n 个数，将这 n 个数按从小到大的顺序输出。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    int a[100];

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

    for (int i = 0; i < n; i ++ )
        for (int j = i + 1; j < n; j ++ )
            if (a[i] > a[j])
                swap(a[i], a[j]);

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

    return 0;
}

练习题5：计算 2 的 N 次方。N≤10000 高精度2的N次幂

思考：2^10000是多少位数字，log10 2^N = Nlog10 2 ≈ 3000位，于是考虑用数组存储一个特别大数字的每一位，例如从个位开始存到a[0] a[1] ... a[n - 1]

#include <bits/stdc++.h>
using namespace std;
const int N = 3010;

int main()
{
    int a[N] = {1};
	int n;
    cin >> n;
    int size = 1;
    
    while (n -- )
    {
        int t = 0; // 进位 
        for (int i = 0; i < size; i ++ )
        {
            t += a[i] * 2;
            a[i] = t % 10;
            t /= 10;
        }
        if (t) a[size ++ ] = t;
    }

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

    return 0;
}

2. 多维数组

多维数组就是数组的数组。

int a[3][4]; // 大小为3的数组，每个元素是含有4个整数的数组。

int arr[10][20][30] = {0}; // 将所有元素初始化为0

// 大小为10的数组，它的每个元素是含有20个数组的数组

// 这些数组的元素是含有30个整数的数组

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int b[3][4] = {         // 三个元素，每个元素都是大小为4的数组
        {0, 1, 2, 3},       // 第1行的初始值
        {4, 5, 6, 7},       // 第2行的初始值
        {8, 9, 10, 11}      // 第3行的初始值
    };

    return 0;
}

练习题：输入一个 n 行 m 列的矩阵，从左上角开始将其按回字形的顺序顺时针打印出来。

蛇形矩阵

#include <bits/stdc++.h>
using namespace std;

int res[100][100];

int main()
{
    int n, m;
    cin >> n >> m;

    int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

    for (int x = 0, y = 0, d = 0, k = 1; k <= n * m; k ++ )
    {
        res[x][y] = k;
        int a = x + dx[d], b = y + dy[d];
        if (a < 0 || a >= n || b < 0 || b >= m || res[a][b])
        {
            d = (d + 1) % 4;
            a = x + dx[d], b = y + dy[d];
        }
        x = a, y = b;
    }

    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ ) cout << res[i][j] << ' ';
        cout << endl;
    }

    return 0;
}

1. memset 更快初始化，清空数组<cstring>

int a[10];
memset(a, 0, 40);

memset(a, 0, sizeof(a))```  // 0  -1

按字节处理 sizeof 可以看成函数 也可以看成操作符 不带括号

2. memcpy 复制数组的值

memcpy(b, a, sizeof a); a[10] = {1} b[10] 把a赋值给b