【数据结构】数组和字符串（一）：数组的基本操作、矩阵的数组表示-摩杜云开发者社区

4.1 数组

数组是一种数据结构，用于存储相同类型的元素序列。它是在内存中连续存储的一组相同类型的数据。数组在计算机科学和编程中扮演着重要的角色，因为它们能够有效地存储和访问大量数据。

4.1.1 数组的存储和寻址

数组的存储和寻址是通过索引来实现的。索引是用于标识数组中单个元素位置的数字。数组的第一个元素通常具有索引0，第二个元素具有索引1，以此类推。通过索引，我们可以直接访问数组中的特定元素。在内存中，数组的元素是连续存储的。数组的第一个元素存储在内存的起始位置，后续元素按照顺序存储在相邻的内存位置中。这种连续存储使得数组的访问非常高效，因为可以通过简单的数学运算来计算出元素的内存地址。对于一维数组，可以使用以下公式来计算元素的内存地址： $$ 地址 = 基地址 + 元素大小 × (索引 - 第一个索引) $$ 其中，基地址是数组的起始内存地址，元素大小是数组中每个元素所占用的字节数，索引是要访问的元素的索引，第一个索引是数组的第一个元素的索引。关于数组的基础知识亦可参考前文：【重拾C语言】六、批量数据组织（一）数组（数组类型、声明与操作、多维数组）

4.1.2 一维数组的基本操作

一维数组的基本操作包括创建数组、访问数组元素、修改数组元素、插入元素、删除元素等。创建数组时需要指定数组的大小，然后可以使用索引来访问和修改数组中的元素。插入和删除元素通常移动其他元素以保持数组的连续性。

1. 创建数组

在C语言中，可以使用以下语法来声明和创建一个一维数组：

数据类型 数组名[数组长度];

例如，创建一个包含5个整数的数组：

int numbers[5];

2. 初始化数组

使用赋值语句为数组的元素进行初始化。可以逐个为数组元素赋值，也可以使用循环来初始化整个数组。

int numbers[5] = {1, 2, 3, 4, 5};  // 逐个赋值初始化

int numbers[5];
for (int i = 0; i < 5; i++) {
    numbers[i] = i + 1;
}  // 使用循环初始化

3. 访问数组元素

使用索引来访问数组中的元素。索引从0开始，最大索引为数组长度减1。

int x = numbers[0];  // 访问第一个元素
int y = numbers[2];  // 访问第三个元素

4. 修改数组元素

通过索引来修改数组中的元素。

numbers[0] = 10;  // 修改第一个元素的值
numbers[2] = 20;  // 修改第三个元素的值

5. 插入元素

在一维数组中，插入元素通常需要移动其他元素的位置：使用循环将插入位置之后的元素向后移动，并将新元素插入到指定位置。

int numbers[5] = {1, 2, 3, 4, 5};
int insertIndex = 2;
int newValue = 10;

// 向后移动元素
for (int i = 4; i > insertIndex; i--) {
    numbers[i] = numbers[i - 1];
}

// 插入新元素
numbers[insertIndex] = newValue;

6. 删除元素

删除元素也需要移动其他元素的位置：使用循环将删除位置之后的元素向前移动，并将最后一个元素置为默认值或移除数组。

int numbers[5] = {1, 2, 3, 4, 5};
int deleteIndex = 2;

// 向前移动元素
for (int i = deleteIndex; i < 4; i++) {
    numbers[i] = numbers[i + 1];
}

// 将最后一个元素置为默认值
numbers[4] = 0;

7.操作整合

#include <stdio.h>

void printArray(int *array){
    for (int i = 0; i < 5; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

int main() {
//    // 创建数组
//    int numbers[5];
//
//    // 初始化数组（逐个赋值）
//    numbers[0] = 0;
//    numbers[1] = 1;
//    numbers[2] = 2;
//    numbers[3] = 3;
//    numbers[4] = 4;
    // 创建数组并初始化
    int numbers[5] = {5, 7, 8, 1, 7};

    // 访问数组元素
    int x = numbers[0];
    printf("访问数组中的1个元素: %d\n", x);

    // 修改数组元素
    numbers[0] = 13;
    printf("修改元素后的数组：");
    printArray(numbers);


    // 插入元素
    int insertIndex = 1;
    int newValue = 14;
    // 向后移动元素
    for (int i = 4; i > insertIndex; i--) {
        numbers[i] = numbers[i - 1];
    }
    // 插入新元素
    numbers[insertIndex] = newValue;
    printf("插入元素后的数组：");
    printArray(numbers);


    // 删除元素
    int deleteIndex = 3;
    // 向前移动元素
    for (int i = deleteIndex; i < 4; i++) {
        numbers[i] = numbers[i + 1];
    }
    printf("删除元素后的数组(不处理最后一个元素)：");
    printArray(numbers);

    // 将最后一个元素置为默认值
    numbers[4] = 0;
    printf("删除元素后的数组(最后一个元素置为默认值)：");
    printArray(numbers);

    return 0;
}

输出：在这里插入图片描述注：为数组提供越界索引保护是十分必要。在很多高级程序设计语言提供的数组类型没有越界索引保护，不检查数组的下标是否合法，如果索引越界且程序尝试访问由索引指定的元素，则可能访问任何随机内存位置中存放的数据。

4.2 矩阵

4.2.1 矩阵的数组表示

矩阵是许多物理问题中出现的数学对象，是一种常用的数据组织方式。计算机工作者关心的是矩阵在计算机中如何存储，以及如何实现矩阵的基本操作。很自然会想到用二维数组存放矩阵，这也是矩阵存储的一个重要直观方法。此外，由前文可知，高级程序设计语言的二维数组采用按行优先次序顺序存储，因此也可以用一维数组来存放矩阵元素，存放次序是按行优先。换句话说，用规模为m×n的一维数组B来存放m行n列的二维矩阵A，且A中元素aij (1≤ i≤ m, 1 ≤ j ≤ n) 应存放在B[(i-1)×n+j-1] 处。数组的基本操作是数组加减，而矩阵的基本操作还有矩阵相乘和矩阵转置等。下面以矩阵乘法为例介绍矩阵的基本操作。矩阵的乘法运算略为复杂，对于矩阵Am×p和Bp×n的乘积Cm×n ，其第i行第j列元素cij的计算公式为 cij = Σ(ai1 * b1j + ai2 * b2j + ... + aip * bpj)

a. 矩阵的二维数组存储及其乘法运算

#include <stdio.h>

void matrix_multiply(int A[][3], int B[][2], int C[][2], int m, int p, int n) {
    int i, j, k;
    
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            C[i][j] = 0;
            for (k = 0; k < p; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

void print_matrix(int matrix[][2], int rows, int cols) {
    int i, j;
    
    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int A[2][3] = {{1, 2, 3},
                   {4, 5, 6}};
    int B[3][2] = {{7, 8},
                   {9, 10},
                   {11, 12}};
    int C[2][2];
    
    int m = 2;  // A的行数
    int p = 3;  // A的列数 / B的行数
    int n = 2;  // B的列数
    
    matrix_multiply(A, B, C, m, p, n);
    
    printf("Result:\n");
    print_matrix(C, m, n);
    
    return 0;
}

matrix_multiply的函数接受三个二维数组作为参数：A，B和C，以及三个整数m，p和n。
- 这些参数分别表示矩阵A的行数、矩阵A的列数（也是矩阵B的行数），以及矩阵B的列数。
- 使用三个嵌套的循环来计算矩阵乘法：
  - 外层的两个循环变量i和j分别用于遍历结果矩阵C的行和列。
  - 在每次迭代中，将矩阵C的当前元素初始化为0。
  - 然后，通过内层的循环变量k来遍历矩阵A的列和矩阵B的行，并将对应元素相乘并累加到矩阵C的当前元素上。

输出：在这里插入图片描述

b. 一维数组存储

#include <stdio.h>

void flattenMatrix(int matrix[][3], int rows, int columns, int array[]) {
    int index = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            array[index] = matrix[i][j];
            index++;
        }
    }
}

int main() {
    int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    int rows = 3;
    int columns = 3;
    int array[rows * columns];

    flattenMatrix(matrix, rows, columns, array);

    // 输出一维数组
    for (int i = 0; i < rows * columns; i++) {
        printf("%d ", array[i]);
    }

    return 0;
}