目录介绍

• 8.1 数组的概念
• 8.2 数组使用
  • 8.2.1 数组的声明
  • 8.2.2 数组初始化
  • 8.2.3 数组访问
  • 8.2.4 数组复制
  • 8.2.5 综合案例与思考
• 8.3 数组长度
• 8.4 多维数组
  • 8.4.1 二维数组
  • 8.4.2 访问多维数组
  • 8.4.3 综合案例与思考
• 8.5 变长数组
• 8.6 数组和指针
• 8.6 数组地址
• 8.7 数组和函数
  • 8.7.1 声明参数数组
  • 8.7.2 变长数组作为参数
  • 8.7.3 数组字面量参数
• 8.8 数组注意事项
  • 8.8.1 索引越界
  • 8.8.2 声明时赋值
• 8.9 数组常见算法
  • 8.9.1 查最大值
  • 8.9.2 数组排序
  • 8.9.3 数组遍历
  • 8.9.4 综合案例与思考

8.1 数组的概念

在 C 语言中，数组是一种用于存储相同类型数据的集合。数组中的每个元素通过索引访问，索引从 0 开始。

数组的基本概念

• 数组：一组相同类型的数据元素。
• 元素：数组中的每个数据项。
• 索引：用于访问数组元素的下标，从 0 开始。

8.2 数组使用

8.2.1 数组的声明

数组是一组相同类型的值，按照顺序储存在一起。数组通过变量名后加方括号表示，方括号里面是数组的成员数量。

语法

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

示例

int arr[5]; // 声明一个包含 5 个整数的数组

注意，声明数组时，必须给出数组的大小。

8.2.2 数组初始化

可以在声明时初始化数组。

语法

数据类型 数组名[数组大小] = {值1, 值2, ...};

示例

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

部分初始化，未初始化的元素默认为 0。

int a[5] = {22, 37, 3490};
// 等同于
int a[5] = {22, 37, 3490, 0, 0};

省略数组大小，如果初始化时指定了所有元素，可以省略数组大小。

C 语言允许省略方括号里面的数组成员数量，这时将根据大括号里面的值的数量，自动确定数组的长度。

int arr[] = {1, 2, 3, 4, 5}; // 数组大小为 5

8.2.3 数组访问

通过索引访问数组元素。

语法

数组名[索引];

示例

int arr[5] = {1, 2, 3, 4, 5};
printf("%d\n", arr[0]); // 输出 1
arr[2] = 10; // 修改第三个元素

8.2.4 数组复制

由于数组名是指针，所以复制数组不能简单地复制数组名。

int* a;
int b[3] = {1, 2, 3};

a = b;

上面的写法，结果不是将数组b复制给数组a，而是让a和b指向同一个数组。

复制数组最简单的方法，还是使用循环，将数组元素逐个进行复制。

for (i = 0; i < N; i++)
    a[i] = b[i];

上面示例中，通过将数组b的成员逐个复制给数组a，从而实现数组的赋值。

另一种方法是使用memcpy()函数（定义在头文件string.h），直接把数组所在的那一段内存，再复制一份。

memcpy(a, b, sizeof(b));

上面示例中，将数组b所在的那段内存，复制给数组a。这种方法要比循环复制数组成员要快。

8.2.5 综合案例与思考

综合案例：数组基本操作大全

#include <stdio.h>
#include <string.h>

int main() {
    // 案例1：数组的各种初始化方式
    int a1[5] = {1, 2, 3, 4, 5};     // 完全初始化
    int a2[5] = {1, 2};               // 部分初始化，其余为0
    int a3[] = {10, 20, 30};          // 自动推断大小
    int a4[5] = {0};                  // 全部初始化为0
    
    printf("=== 初始化方式 ===\n");
    printf("a2: "); for(int i=0;i<5;i++) printf("%d ",a2[i]); printf("\n");
    printf("a4: "); for(int i=0;i<5;i++) printf("%d ",a4[i]); printf("\n");
    
    // 案例2：数组复制的两种方式
    printf("\n=== 数组复制 ===\n");
    int src[] = {11, 22, 33, 44, 55};
    int dst1[5], dst2[5];
    
    // 方式1：循环复制
    for (int i = 0; i < 5; i++) dst1[i] = src[i];
    
    // 方式2：memcpy
    memcpy(dst2, src, sizeof(src));
    
    printf("src:  "); for(int i=0;i<5;i++) printf("%d ",src[i]); printf("\n");
    printf("dst1: "); for(int i=0;i<5;i++) printf("%d ",dst1[i]); printf("\n");
    printf("dst2: "); for(int i=0;i<5;i++) printf("%d ",dst2[i]); printf("\n");
    
    // 案例3：数组元素的插入和删除（逻辑操作）
    printf("\n=== 数组插入与删除 ===\n");
    int arr[10] = {10, 20, 30, 40, 50};
    int len = 5;
    
    // 在索引2处插入25
    for (int i = len; i > 2; i--) arr[i] = arr[i-1];
    arr[2] = 25;
    len++;
    printf("插入25后: "); for(int i=0;i<len;i++) printf("%d ",arr[i]); printf("\n");
    
    // 删除索引3处的元素
    for (int i = 3; i < len - 1; i++) arr[i] = arr[i+1];
    len--;
    printf("删除[3]后: "); for(int i=0;i<len;i++) printf("%d ",arr[i]); printf("\n");
    
    return 0;
}

原理说明：数组在内存中是连续存储的，这意味着：1）通过首地址 + 偏移量可以O(1)时间访问任意元素；2）插入和删除操作需要移动大量元素，时间复杂度为O(n)；3）memcpy 利用CPU的块拷贝指令，比逐元素循环更快。数组未初始化的元素在局部变量中是未定义值（垃圾值），在全局/静态变量中会被自动初始化为0。

思考题：

1. int a[5] = {0} 和 int a[5] = {} 有什么区别？后者在C和C++中是否都合法？
2. memcpy 和 memmove 有什么区别？在什么情况下必须用 memmove？
3. 数组的插入操作为什么要从后往前移动元素？如果从前往后会怎样？

sizeof运算符会返回整个数组的字节长度。

int a[] = {22, 37, 3490};
int arrLen = sizeof(a); // 12

上面示例中，sizeof返回数组a的字节长度是12。

由于数组成员都是同一个类型，每个成员的字节长度都是一样的，所以数组整体的字节长度除以某个数组成员的字节长度，就可以得到数组的成员数量。

sizeof(a) / sizeof(a[0])

上面示例中，sizeof(a)是整个数组的字节长度，sizeof(a[0])是数组成员的字节长度，相除就是数组的成员数量。

注意，sizeof返回值的数据类型是size_t，所以sizeof(a) / sizeof(a[0])的数据类型也是size_t。在printf()里面的占位符，要用%zd或%zu。

int x[12];

printf("%zu\n", sizeof(x));     // 48
printf("%zu\n", sizeof(int));  // 4
printf("%zu\n", sizeof(x) / sizeof(int)); // 12

上面示例中，sizeof(x) / sizeof(int)就可以得到数组成员数量12。

8.4 多维数组

8.4.1 二维数组

C 语言允许声明多个维度的数组，有多少个维度，就用多少个方括号，比如二维数组就使用两个方括号。

语法

数据类型 数组名[行数][列数];

示例

int mat[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

上面示例声明了一个二维数组，第一个维度有3个成员，第二个维度也有3个成员。

8.4.2 访问多维数组

printf("%d\n", mat[1][2]); // 输出 6

8.4.3 综合案例与思考

综合案例：二维数组的实际应用

#include <stdio.h>

int main() {
    // 案例1：矩阵转置
    int mat[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
    int trans[3][3];
    
    printf("=== 矩阵转置 ===\n");
    printf("原矩阵:\n");
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            trans[j][i] = mat[i][j];
            printf("%2d ", mat[i][j]);
        }
        printf("\n");
    }
    printf("转置后:\n");
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) printf("%2d ", trans[i][j]);
        printf("\n");
    }
    
    // 案例2：矩阵加法
    printf("\n=== 矩阵加法 ===\n");
    int a[2][3] = {{1,2,3},{4,5,6}};
    int b[2][3] = {{7,8,9},{10,11,12}};
    int c[2][3];
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 3; j++)
            c[i][j] = a[i][j] + b[i][j];
    
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 3; j++) printf("%3d ", c[i][j]);
        printf("\n");
    }
    
    // 案例3：在二维数组中查找鞍点
    printf("\n=== 查找鞍点 ===\n");
    int m[3][3] = {{1,2,3},{8,5,6},{4,7,9}};
    for (int i = 0; i < 3; i++) {
        // 找第i行最大值
        int max_j = 0;
        for (int j = 1; j < 3; j++)
            if (m[i][j] > m[i][max_j]) max_j = j;
        
        // 检查该元素是否为所在列最小值
        int is_saddle = 1;
        for (int k = 0; k < 3; k++)
            if (m[k][max_j] < m[i][max_j]) { is_saddle = 0; break; }
        
        if (is_saddle)
            printf("鞍点: m[%d][%d] = %d\n", i, max_j, m[i][max_j]);
    }
    
    return 0;
}

原理说明：二维数组 int a[M][N] 在内存中是按行存储的（Row-major order），即 a[0][0], a[0][1], ..., a[0][N-1], a[1][0], ...。元素 a[i][j] 的地址为 基地址 + (i * N + j) * sizeof(int)。因此，按行遍历（内层循环是列索引）比按列遍历更快，因为前者的内存访问是连续的，能充分利用CPU缓存（Cache Line）。

思考题：

1. 二维数组在内存中是按行存储还是按列存储？Fortran语言呢？这对性能有什么影响？
2. int a[3][4] 能否用 int *p = (int *)a 来访问？p[5] 对应原数组的哪个元素？
3. 如何用一维数组模拟二维数组？这种做法有什么优势？

数组声明的时候，数组长度除了使用常量，也可以使用变量。这叫做变长数组（variable-length array，简称 VLA）。

int n = x + y;
int arr[n];

上面示例中，数组arr就是变长数组，因为它的长度取决于变量n的值，编译器没法事先确定，只有运行时才能知道n是多少。

变长数组的根本特征，就是数组长度只有运行时才能确定。它的好处是程序员不必在开发时，随意为数组指定一个估计的长度，程序可以在运行时为数组分配精确的长度。

任何长度需要运行时才能确定的数组，都是变长数组。

int i = 10;

int a1[i];
int a2[i + 5];
int a3[i + k];

上面示例中，三个数组的长度都需要运行代码才能知道，编译器并不知道它们的长度，所以它们都是变长数组。

变长数组也可以用于多维数组。

int m = 4;
int n = 5;
int c[m][n];

上面示例中，c[m][n]就是二维变长数组。

8.6 数组和指针

C 语言里面，数组名可以进行加法和减法运算，等同于在数组成员之间前后移动，即从一个成员的内存地址移动到另一个成员的内存地址。比如，a + 1返回下一个成员的地址，a - 1返回上一个成员的地址。

int a[5] = {11, 22, 33, 44, 55};

for (int i = 0; i < 5; i++) {
    printf("%d\n", *(a + i));
}

数组名是数组首元素的地址。

示例

int arr[5] = {1, 2, 3, 4, 5};
int *p = arr; // p 指向 arr[0]
printf("%d\n", *p); // 输出 1

指针算术

printf("%d\n", *(p + 2)); // 输出 3

8.6 数组地址

数组是一连串连续储存的同类型值，只要获得起始地址（首个成员的内存地址），就能推算出其他成员的地址。请看下面的例子。

int a[5] = {11, 22, 33, 44, 55};
int* p;

p = &a[0];

printf("%d\n", *p);  // Prints "11"

上面示例中，&a[0]就是数组a的首个成员11的内存地址，也是整个数组的起始地址。反过来，从这个地址（*p），可以获得首个成员的值11。

由于数组的起始地址是常用操作，&array[0]的写法有点麻烦，C 语言提供了便利写法，数组名等同于起始地址，也就是说，数组名就是指向第一个成员（array[0]）的指针。

int a[5] = {11, 22, 33, 44, 55};

int* p = &a[0];
// 等同于
int* p = a;

上面示例中，&a[0]和数组名a是等价的。

这样的话，如果把数组名传入一个函数，就等同于传入一个指针变量。在函数内部，就可以通过这个指针变量获得整个数组。

函数接受数组作为参数，函数原型可以写成下面这样。

// 写法一
int sum(int arr[], int len);
// 写法二
int sum(int* arr, int len);

上面示例中，传入一个整数数组，与传入一个整数指针是同一回事，数组符号[]与指针符号*是可以互换的。下一个例子是通过数组指针对成员求和。

int sum(int* arr, int len) {
    int i;
    int total = 0;
    
    // 假定数组有 10 个成员
    for (i = 0; i < len; i++) {
        total += arr[i];
    }
    return total;
}

上面示例中，传入函数的是一个指针arr（也是数组名）和数组长度，通过指针获取数组的每个成员，从而求和。

*和&运算符也可以用于多维数组。

int a[4][2];

// 取出 a[0][0] 的值
*(a[0]);
// 等同于
**a

上面示例中，由于a[0]本身是一个指针，指向第二维数组的第一个成员a[0][0]。所以，(a[0])取出的是a[0][0]的值。至于**a，就是对a进行两次运算，第一次取出的是a[0]，第二次取出的是a[0][0]。同理，二维数组的&a[0][0]等同于*a。

注意，数组名指向的地址是不能更改的。声明数组时，编译器自动为数组分配了内存地址，这个地址与数组名是绑定的，不可更改，下面的代码会报错。

int ints[100];
ints = NULL; // 报错

上面示例中，重新为数组名赋值，改变原来的内存地址，就会报错。

这也导致不能将一个数组名赋值给另外一个数组名。

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

// 写法一
int b[5] = a; // 报错

// 写法二
int b[5];
b = a; // 报错

上面两种写法都会更改数组b的地址，导致报错。

8.7 数组和函数

8.7.1 声明参数数组

数组作为函数的参数，一般会同时传入数组名和数组长度。

int sum_array(int a[], int n) {
// ...
}

int a[] = {3, 5, 7, 3};
int sum = sum_array(a, 4);

上面示例中，函数sum_array()的第一个参数是数组本身，也就是数组名，第二个参数是数组长度。

由于数组名就是一个指针，如果只传数组名，那么函数只知道数组开始的地址，不知道结束的地址，所以才需要把数组长度也一起传入。

8.7.2 变长数组作为参数

变长数组作为函数参数时，写法略有不同。

int sum_array(int n, int a[n]) {
// ...
}

int a[] = {3, 5, 7, 3};
int sum = sum_array(4, a);

上面示例中，数组a[n]是一个变长数组，它的长度取决于变量n的值，只有运行时才能知道。所以，变量n作为参数时，顺序一定要在变长数组前面，这样运行时才能确定数组a[n]的长度，否则就会报错。

因为函数原型可以省略参数名，所以变长数组的原型中，可以使用*代替变量名，也可以省略变量名。

int sum_array(int, int [*]);
int sum_array(int, int []);

上面两种变长函数的原型写法，都是合法的。

变长数组作为函数参数有一个好处，就是多维数组的参数声明，可以把后面的维度省掉了。

8.7.3 数组字面量参数

C 语言允许将数组字面量作为参数，传入函数。

// 数组变量作为参数
int a[] = {2, 3, 4, 5};
int sum = sum_array(a, 4);

// 数组字面量作为参数
int sum = sum_array((int []){2, 3, 4, 5}, 4);

上面示例中，两种写法是等价的。第二种写法省掉了数组变量的声明，直接将数组字面量传入函数。{2, 3, 4, 5}是数组值的字面量，(int [])类似于强制的类型转换，告诉编译器怎么理解这组值。

8.8 数组注意事项

8.8.1 索引越界

索引越界：访问超出数组范围的索引会导致未定义行为。 示例：

int arr[5] = {1, 2, 3, 4, 5};
printf("%d\n", arr[5]); // 错误：索引越界

8.8.2 声明时赋值

注意，使用大括号赋值时，必须在数组声明时赋值，否则编译时会报错。

int a[5];
a = {22, 37, 3490, 18, 95}; // 报错

上面代码中，数组a声明之后再进行大括号赋值，导致报错。

报错的原因是，C 语言规定，数组变量一旦声明，就不得修改变量指向的地址，具体会在后文解释。由于同样的原因，数组赋值之后，再用大括号修改值，也是不允许的。

2. 数组大小：

   • 数组大小必须是常量表达式。
   • 示例：

     int size = 5;
     int arr[size]; // 错误：C89 标准不支持变量作为数组大小
     

3. 数组名是常量指针：

   • 数组名是数组首元素的地址，不能修改。
   • 示例：

     int arr[5] = {1, 2, 3, 4, 5};
     arr++; // 错误：数组名是常量指针
     

4. 数组初始化：

   • 未初始化的数组元素值是未定义的。

8.9 数组常见算法

8.9.1 查最大值

int findMax(int arr[], int size) {
    int max = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

8.9.2 数组排序

void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

8.9.3 数组遍历

void printMatrix(int mat[3][3]) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", mat[i][j]);
        }
        printf("\n");
    }
}

8.9.4 综合案例与思考

综合案例：数组算法综合实战

#include <stdio.h>
#include <string.h>

// 冒泡排序
void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;  // 优化：无交换则已有序
    }
}

// 二分查找（数组必须已排序）
int binary_search(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;  // 防溢出
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

// 数组去重（原地，要求已排序）
int remove_duplicates(int arr[], int n) {
    if (n <= 1) return n;
    int new_len = 1;
    for (int i = 1; i < n; i++) {
        if (arr[i] != arr[new_len - 1]) {
            arr[new_len++] = arr[i];
        }
    }
    return new_len;
}

void print_arr(const char *label, int arr[], int n) {
    printf("%s: ", label);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90, 34, 25};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    print_arr("原始数组", arr, n);
    
    // 排序
    bubble_sort(arr, n);
    print_arr("排序后  ", arr, n);
    
    // 二分查找
    int target = 34;
    int idx = binary_search(arr, n, target);
    printf("查找 %d: %s (索引=%d)\n", target, idx >= 0 ? "找到" : "未找到", idx);
    
    // 去重
    int new_len = remove_duplicates(arr, n);
    print_arr("去重后  ", arr, new_len);
    
    return 0;
}

原理说明：冒泡排序的时间复杂度为 O(n²)，通过提前终止优化（swapped 标志）可在最好情况下达到 O(n)。二分查找要求数组有序，时间复杂度为 O(log n)，注意用 low + (high - low) / 2 代替 (low + high) / 2 来防止整数溢出。原地去重利用已排序的特性，用双指针法在 O(n) 时间内完成。这些基础算法是更复杂数据结构和算法的基石。

思考题：

1. 冒泡排序、选择排序、插入排序的时间复杂度都是 O(n²)，但实际性能有什么差异？哪个在"几乎有序"的数组上最快？
2. 二分查找中 mid = (low + high) / 2 在什么情况下会溢出？low + (high - low) / 2 是如何解决的？
3. C标准库提供了 qsort 和 bsearch 函数，如何使用它们？与手写版本相比有什么优势？