面试题：C语言二维数组存储顺序及访问相关

Question

在C语言中，假设有一个二维数组`int arr[3][4]`，请阐述其在内存中的存储顺序，并编写代码实现按行和按列两种方式遍历该数组，解释两种遍历方式在内存访问上的差异。

Answer 1

1. 内存存储顺序：
   • 在C语言中，二维数组int arr[3][4]在内存中是按行优先存储的。也就是说，先存储第一行的所有元素，接着存储第二行的所有元素，最后存储第三行的所有元素。例如，arr[0][0]，arr[0][1]，arr[0][2]，arr[0][3]，然后是arr[1][0]，arr[1][1]等。
2. 按行遍历代码：

#include <stdio.h>

int main() {
    int arr[3][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };
    int i, j;
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 4; j++) {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
    return 0;
}

3. 按列遍历代码：

#include <stdio.h>

int main() {
    int arr[3][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };
    int i, j;
    for (j = 0; j < 4; j++) {
        for (i = 0; i < 3; i++) {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
    return 0;
}

4. 内存访问差异：
   • 按行遍历：由于数组在内存中是按行优先存储的，按行遍历能够连续地访问内存中的元素，这种访问模式具有较好的空间局部性，因为每次访问的元素在内存中是相邻的，缓存命中率较高，对于现代CPU的缓存机制较为友好，执行效率相对较高。
   • 按列遍历：按列遍历会跳跃式地访问内存。例如，访问arr[0][0]后，下一个访问arr[1][0]，这两个元素在内存中并不是相邻的，它们之间间隔了4 - 1个int类型元素的大小（这里int假设为4字节）。这种非连续的内存访问方式会降低缓存命中率，从而导致性能下降，相比按行遍历效率较低。