第6章 数组

1. 数组的深入理解

1.1 数组的基本概念

数组是一种存储相同类型元素的集合，这些元素在内存中连续存储。数组的大小在声明时确定，之后不能改变。

1.1.1 数组的内存布局

数组在内存中是连续存储的，每个元素占用相同大小的内存空间。对于一个类型为 type 的数组 array_name[size]，其内存布局如下：

1
2
3
4
5
+---------------------+---------------------+---------------------+---+---------------------+
| array_name[0]       | array_name[1]       | array_name[2]       |...| array_name[size-1]   |
+---------------------+---------------------+---------------------+---+---------------------+
| 内存地址: base      | 内存地址: base+size | 内存地址: base+2*size|...| 内存地址: base+(size-1)*size |
+---------------------+---------------------+---------------------+---+---------------------+

其中，base 是数组第一个元素的内存地址，size 是单个元素的大小（以字节为单位）。

1.1.2 数组的声明和初始化

一维数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 声明一维数组
type array_name[size];

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

// 初始化一维数组
int numbers[5] = {1, 2, 3, 4, 5};  // 完整初始化
int numbers[] = {1, 2, 3, 4, 5};   // 自动计算大小
int numbers[5] = {1, 2};            // 部分初始化，其余元素为 0
int numbers[5] = {0};               // 所有元素初始化为 0

// C99 及以上支持的指定初始化器
int numbers[5] = {[0] = 1, [2] = 3, [4] = 5};  // 只初始化指定位置的元素
二维数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 声明二维数组
type array_name[rows][columns];

// 示例
int matrix[3][3];  // 声明一个 3x3 的整数矩阵

// 初始化二维数组
int matrix[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

int matrix[3][3] = {1, 2, 3, 4, 5, 6, 7, 8, 9};  // 线性初始化
int matrix[][3] = {{1, 2, 3}, {4, 5, 6}};        // 自动计算行数

// C99 及以上支持的指定初始化器
int matrix[3][3] = {
    [0][0] = 1,
    [1][1] = 5,
    [2][2] = 9
};
多维数组

多维数组的声明和初始化方式类似于二维数组，只是维度更多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 声明三维数组
int cube[2][3][4];  // 2 层，每层 3 行 4 列

// 初始化三维数组
int cube[2][3][4] = {
    {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    },
    {
        {13, 14, 15, 16},
        {17, 18, 19, 20},
        {21, 22, 23, 24}
    }
};

1.2 数组的访问

数组元素通过索引访问，索引从 0 开始。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int numbers[5] = {1, 2, 3, 4, 5};

// 访问单个元素
printf("第一个元素：%d\n", numbers[0]);  // 输出 1
printf("最后一个元素：%d\n", numbers[4]);  // 输出 5

// 修改元素
numbers[2] = 10;  // 将第三个元素修改为 10

// 遍历数组
for (int i = 0; i < 5; i++)
{
    printf("numbers[%d] = %d\n", i, numbers[i]);
}

// 遍历二维数组
int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
for (int i = 0; i < 3; i++)
{
    for (int j = 0; j < 3; j++)
    {
        printf("matrix[%d][%d] = %d\n", i, j, matrix[i][j]);
    }
}

1.2.1 数组的边界检查

C 语言不进行数组边界检查，访问超出数组范围的元素会导致未定义行为。

1
2
int numbers[5] = {1, 2, 3, 4, 5};
numbers[10] = 100;  // 越界访问，未定义行为

为了避免数组越界，可以采取以下措施：

  • 使用常量定义数组大小
  • 在循环中使用正确的边界条件
  • 使用静态分析工具检测潜在的越界访问

1.3 数组的特性

  • 数组大小固定 - 数组一旦声明，大小不能改变
  • 连续存储 - 数组元素在内存中连续存储
  • 零基索引 - 数组索引从 0 开始
  • 数组名是常量指针 - 数组名指向数组的第一个元素，是一个常量指针
  • 数组长度计算 - 使用 sizeof 运算符可以计算数组的总大小和单个元素的大小
1
2
3
4
int numbers[5];
printf("数组总大小：%zu 字节\n", sizeof(numbers));       // 输出 20（假设 int 为 4 字节）
printf("单个元素大小：%zu 字节\n", sizeof(numbers[0]));  // 输出 4
printf("数组长度：%zu\n", sizeof(numbers) / sizeof(numbers[0]));  // 输出 5

1.4 变长数组（VLA）

C99 引入了变长数组（Variable Length Array），允许使用变量作为数组大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>

void print_array(int n, int arr[n])
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(void)
{
    int size;
    printf("请输入数组大小：");
    scanf("%d", &size);
    
    int numbers[size];  // 变长数组
    
    for (int i = 0; i < size; i++)
    {
        numbers[i] = i + 1;
    }
    
    print_array(size, numbers);
    
    return 0;
}

注意：

  • 变长数组不能初始化
  • 变长数组的大小在运行时确定
  • 变长数组只在块作用域内有效
  • 不是所有编译器都支持变长数组（如 MSVC）

1.5 数组作为函数参数

当数组作为函数参数传递时，实际上传递的是数组第一个元素的地址。

1.5.1 数组作为函数参数的机制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 函数声明
void print_array(int arr[], int size);
// 等价于
void print_array(int *arr, int size);

// 函数定义
void print_array(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 调用函数
int numbers[] = {1, 2, 3, 4, 5};
print_array(numbers, 5);

1.5.2 多维数组作为函数参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 函数声明
void print_matrix(int matrix[][3], int rows);
// 等价于
void print_matrix(int (*matrix)[3], int rows);

// 函数定义
void print_matrix(int matrix[][3], int rows)
{
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

// 调用函数
int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};
print_matrix(matrix, 2);

2. 指针的深入理解

2.1 指针的基本概念

指针是一种存储内存地址的变量。指针变量本身也占用内存空间，其大小取决于系统架构（32位系统为4字节，64位系统为8字节）。

2.1.1 指针的内存布局

对于一个类型为 type * 的指针变量 p，其内存布局如下：

1
2
3
4
5
6
7
+---------------------+
| p                   |
+---------------------+
| 内存地址: &p         |
+---------------------+
| 值: 指向的内存地址   |
+---------------------+

其中，&p 是指针变量本身的内存地址，而指针变量的值是它指向的内存地址。

2.2 指针的声明和初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 声明指针
type *pointer_name;

// 示例
int *p;         // 声明一个指向整数的指针
float *fp;      // 声明一个指向浮点数的指针
char *cp;       // 声明一个指向字符的指针

// 初始化指针
int x = 10;
int *p = &x;    // 初始化指针 p，使其指向变量 x

// 空指针
int *p = NULL;  // 初始化为空指针
int *p = 0;     // 初始化为空指针（0 等同于 NULL）

// C11 引入的空指针常量
int *p = nullptr;  // 仅在 C++11 及以上或支持 C11 的编译器中可用

2.3 指针的解引用

使用 * 运算符可以访问指针指向的变量的值。

1
2
3
4
5
6
7
8
9
10
int x = 10;
int *p = &x;

printf("x 的值：%d\n", x);      // 输出 10
printf("p 的值：%p\n", p);      // 输出 x 的地址
printf("*p 的值：%d\n", *p);    // 输出 10，解引用

// 修改指针指向的变量的值
*p = 20;
printf("x 的新值：%d\n", x);    // 输出 20

2.4 指针的算术运算

指针支持以下算术运算：

  • 加法 - 指针 + 整数
  • 减法 - 指针 - 整数
  • 指针相减 - 两个指针相减
  • 比较 - 比较两个指针的大小

2.4.1 指针算术的本质

指针算术的结果取决于指针指向的类型。对于一个类型为 type * 的指针 p，p + n 表示指向 p 指向的位置之后的第 n 个 type 类型的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int numbers[] = {1, 2, 3, 4, 5};
int *p = numbers;  // 指向第一个元素

printf("*p = %d\n", *p);      // 输出 1
printf("p 的地址：%p\n", (void *)p);

p++;                          // 指针向后移动一个元素（4字节）
printf("*p = %d\n", *p);      // 输出 2
printf("p 的地址：%p\n", (void *)p);

p += 2;                       // 指针向后移动两个元素（8字节）
printf("*p = %d\n", *p);      // 输出 4
printf("p 的地址：%p\n", (void *)p);

int *q = &numbers[4];         // 指向最后一个元素
printf("q - p = %ld\n", q - p);  // 输出 1，两个指针之间的元素个数

// 比较指针
if (p < q)
{
    printf("p 指向的元素在 q 指向的元素之前\n");
}

2.5 指针的类型转换

指针的类型转换需要谨慎使用，不正确的类型转换可能导致未定义行为。

1
2
3
4
5
6
7
8
9
10
11
12
int x = 10;
int *p = &x;

// 隐式类型转换
void *vp = p;  // 任何指针都可以隐式转换为 void *

// 显式类型转换
int *p2 = (int *)vp;  // 需要显式转换回原类型

// 不同类型之间的转换
char *cp = (char *)&x;  // 将 int * 转换为 char *
printf("*cp = %d\n", *cp);  // 输出 x 的第一个字节的值

2.6 空指针和野指针

2.6.1 空指针

空指针是指向空地址的指针，通常使用 NULL 或 0 表示。

1
2
3
4
5
6
7
int *p = NULL;

// 检查空指针
if (p != NULL)
{
    // 使用指针
}

2.6.2 野指针

野指针是指向无效内存地址的指针，通常由以下原因产生：

  • 未初始化的指针
  • 已释放内存的指针
  • 越界访问的指针
1
2
3
4
5
6
7
8
9
10
11
// 未初始化的指针
int *p;  // 野指针

// 已释放内存的指针
int *p = (int *)malloc(sizeof(int));
free(p);
p = NULL;  // 释放后应将指针置为空

// 越界访问的指针
int numbers[5];
int *p = &numbers[5];  // 指向数组末尾之后，野指针

2.7 指针数组

指针数组是一个存储指针的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 声明指针数组
type *array_name[size];

// 示例：字符串数组
char *names[] = {
    "Alice",
    "Bob",
    "Charlie",
    "David"
};

// 访问指针数组元素
for (int i = 0; i < 4; i++)
{
    printf("%s\n", names[i]);
}

// 示例：整数指针数组
int a = 10, b = 20, c = 30;
int *ptr_array[] = {&a, &b, &c};

// 访问指针数组元素
for (int i = 0; i < 3; i++)
{
    printf("%d\n", *ptr_array[i]);
}

2.8 指向指针的指针

指向指针的指针是一种存储指针地址的变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 声明指向指针的指针
type **pointer_name;

// 示例
int x = 10;
int *p = &x;
int **pp = &p;

printf("x = %d\n", x);        // 输出 10
printf("*p = %d\n", *p);      // 输出 10
printf("**pp = %d\n", **pp);  // 输出 10

// 修改值
**pp = 20;
printf("x = %d\n", x);        // 输出 20

// 指向指针的指针的应用：二维动态数组
int **matrix;
int rows = 3, cols = 3;

// 分配内存
matrix = (int **)malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++)
{
    matrix[i] = (int *)malloc(cols * sizeof(int));
}

// 使用
for (int i = 0; i < rows; i++)
{
    for (int j = 0; j < cols; j++)
    {
        matrix[i][j] = i * cols + j + 1;
    }
}

// 释放内存
for (int i = 0; i < rows; i++)
{
    free(matrix[i]);
}
free(matrix);

2.9 函数指针

函数指针是指向函数的指针，可以用于回调函数、函数表等场景。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 声明函数指针
type (*pointer_name)(parameters);

// 示例
int add(int a, int b)
{
    return a + b;
}

int subtract(int a, int b)
{
    return a - b;
}

// 声明函数指针
int (*operation)(int, int);

// 初始化函数指针
operation = add;
printf("3 + 4 = %d\n", operation(3, 4));  // 输出 7

operation = subtract;
printf("3 - 4 = %d\n", operation(3, 4));  // 输出 -1

// 函数指针数组
int (*operations[])(int, int) = {add, subtract};
printf("3 + 4 = %d\n", operations[0](3, 4));  // 输出 7
printf("3 - 4 = %d\n", operations[1](3, 4));  // 输出 -1

3. 数组和指针的关系

3.1 数组名作为指针

数组名本质上是一个指向数组第一个元素的常量指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
int numbers[] = {1, 2, 3, 4, 5};
int *p = numbers;  // 等同于 int *p = &numbers[0];

// 使用指针遍历数组
for (int i = 0; i < 5; i++)
{
    printf("%d ", *(p + i));  // 等同于 numbers[i]
}
printf("\n");

// 数组下标访问等同于指针解引用
printf("numbers[2] = %d\n", numbers[2]);    // 输出 3
printf("*(numbers + 2) = %d\n", *(numbers + 2));  // 输出 3

3.2 数组下标和指针算术的等价性

对于数组 arr 和整数 i，arr[i] 等价于 *(arr + i)。

1
2
3
4
5
6
7
8
9
10
11
int numbers[] = {1, 2, 3, 4, 5};
int *p = numbers;

// 以下表达式等价
numbers[2] = 10;
*(numbers + 2) = 10;
p[2] = 10;
*(p + 2) = 10;

// 甚至可以写成这样（不推荐）
2[numbers] = 10;  // 等价于 numbers[2]，因为加法满足交换律

3.3 多维数组与指针

多维数组在内存中是线性存储的，其元素按行优先顺序排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 二维数组
int matrix[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

// 内存布局：1, 2, 3, 4, 5, 6, 7, 8, 9

// 指向一维数组的指针
int (*p)[3] = matrix;

// 访问元素
printf("matrix[1][2] = %d\n", matrix[1][2]);    // 输出 6
printf("*(*(p + 1) + 2) = %d\n", *(*(p + 1) + 2));  // 输出 6
printf("p[1][2] = %d\n", p[1][2]);  // 输出 6

4. 动态内存管理

4.1 内存分配函数

C 语言提供了以下动态内存分配函数：

  • malloc - 分配指定大小的内存
  • calloc - 分配指定数量和大小的内存，并初始化为 0
  • realloc - 调整已分配内存的大小
  • free - 释放已分配的内存

这些函数都在 stdlib.h 头文件中声明。

4.2 内存分配示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    // 使用 malloc 分配内存
    int *arr = (int *)malloc(5 * sizeof(int));
    if (arr == NULL)
    {
        printf("内存分配失败\n");
        return 1;
    }
    
    // 初始化数组
    for (int i = 0; i < 5; i++)
    {
        arr[i] = i + 1;
    }
    
    // 打印数组
    for (int i = 0; i < 5; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    // 使用 realloc 调整内存大小
    int *new_arr = (int *)realloc(arr, 10 * sizeof(int));
    if (new_arr == NULL)
    {
        printf("内存分配失败\n");
        free(arr);
        return 1;
    }
    arr = new_arr;
    
    // 初始化新分配的元素
    for (int i = 5; i < 10; i++)
    {
        arr[i] = i + 1;
    }
    
    // 打印数组
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    // 使用 free 释放内存
    free(arr);
    
    // 使用 calloc 分配内存
    int *arr2 = (int *)calloc(5, sizeof(int));
    if (arr2 == NULL)
    {
        printf("内存分配失败\n");
        return 1;
    }
    
    // 打印数组（已初始化为 0）
    for (int i = 0; i < 5; i++)
    {
        printf("%d ", arr2[i]);
    }
    printf("\n");
    
    // 释放内存
    free(arr2);
    
    return 0;
}

4.3 内存管理的常见问题

4.3.1 内存泄漏

内存泄漏是指程序分配了内存但没有释放，导致内存使用量不断增加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 内存泄漏示例
void leak_memory(void)
{
    int *arr = (int *)malloc(100 * sizeof(int));
    // 没有调用 free(arr);
}

int main(void)
{
    for (int i = 0; i < 1000; i++)
    {
        leak_memory();  // 每次调用都会泄漏内存
    }
    return 0;
}

4.3.2 双重释放

双重释放是指对同一块内存多次调用 free，导致未定义行为。

1
2
3
int *p = (int *)malloc(sizeof(int));
free(p);
free(p);  // 双重释放，未定义行为

4.3.3 悬垂指针

悬垂指针是指指向已释放内存的指针。

1
2
3
int *p = (int *)malloc(sizeof(int));
free(p);
*p = 10;  // 悬垂指针，未定义行为

4.4 内存管理的最佳实践

  • 始终检查内存分配是否成功
  • 使用完内存后及时释放
  • 释放内存后将指针置为空
  • 避免双重释放
  • 使用适当的内存分配函数
  • 考虑使用内存池管理频繁分配的小内存

5. 高级应用

5.1 动态数组

动态数组是使用动态内存分配实现的可变大小的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <stdio.h>
#include <stdlib.h>

// 动态数组结构
typedef struct {
    int *data;
    int size;
    int capacity;
} DynamicArray;

// 初始化动态数组
DynamicArray *create_dynamic_array(int initial_capacity)
{
    DynamicArray *array = (DynamicArray *)malloc(sizeof(DynamicArray));
    if (array == NULL)
    {
        return NULL;
    }
    
    array->data = (int *)malloc(initial_capacity * sizeof(int));
    if (array->data == NULL)
    {
        free(array);
        return NULL;
    }
    
    array->size = 0;
    array->capacity = initial_capacity;
    
    return array;
}

// 添加元素
void add_element(DynamicArray *array, int element)
{
    if (array->size >= array->capacity)
    {
        // 扩容
        int new_capacity = array->capacity * 2;
        int *new_data = (int *)realloc(array->data, new_capacity * sizeof(int));
        if (new_data == NULL)
        {
            return;
        }
        
        array->data = new_data;
        array->capacity = new_capacity;
    }
    
    array->data[array->size++] = element;
}

// 释放动态数组
void free_dynamic_array(DynamicArray *array)
{
    if (array != NULL)
    {
        free(array->data);
        free(array);
    }
}

int main(void)
{
    DynamicArray *array = create_dynamic_array(5);
    if (array == NULL)
    {
        printf("内存分配失败\n");
        return 1;
    }
    
    // 添加元素
    for (int i = 0; i < 10; i++)
    {
        add_element(array, i + 1);
    }
    
    // 打印元素
    for (int i = 0; i < array->size; i++)
    {
        printf("%d ", array->data[i]);
    }
    printf("\n");
    
    // 释放内存
    free_dynamic_array(array);
    
    return 0;
}

5.2 指针数组的高级应用

指针数组可以用于实现字符串表、命令表等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 命令表示例
#include <stdio.h>

void help_command(void)
{
    printf("帮助命令\n");
}

void version_command(void)
{
    printf("版本命令\n");
}

void exit_command(void)
{
    printf("退出命令\n");
}

// 命令结构
typedef struct {
    char *name;
    void (*func)(void);
} Command;

// 命令表
Command commands[] = {
    {"help", help_command},
    {"version", version_command},
    {"exit", exit_command},
    {NULL, NULL}  // 结束标记
};

// 执行命令
void execute_command(char *name)
{
    for (int i = 0; commands[i].name != NULL; i++)
    {
        if (strcmp(name, commands[i].name) == 0)
        {
            commands[i].func();
            return;
        }
    }
    printf("未知命令\n");
}

int main(void)
{
    execute_command("help");
    execute_command("version");
    execute_command("exit");
    execute_command("unknown");
    
    return 0;
}

5.3 函数指针的高级应用

函数指针可以用于实现回调函数、策略模式等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// 回调函数示例
#include <stdio.h>

// 回调函数类型
typedef int (*CompareFunction)(int, int);

// 比较函数
int ascending(int a, int b)
{
    return a - b;
}

int descending(int a, int b)
{
    return b - a;
}

// 排序函数
void sort(int arr[], int size, CompareFunction compare)
{
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = 0; j < size - i - 1; j++)
        {
            if (compare(arr[j], arr[j + 1]) > 0)
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 打印数组
void print_array(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(void)
{
    int numbers[] = {5, 2, 8, 1, 9};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    
    printf("原始数组：");
    print_array(numbers, size);
    
    // 升序排序
    sort(numbers, size, ascending);
    printf("升序排序：");
    print_array(numbers, size);
    
    // 降序排序
    sort(numbers, size, descending);
    printf("降序排序：");
    print_array(numbers, size);
    
    return 0;
}

6. 性能优化

6.1 数组和指针操作的性能比较

在大多数情况下，数组下标访问和指针算术的性能差异很小，因为编译器会进行优化。

1
2
3
4
5
6
7
8
9
10
11
// 数组下标访问
for (int i = 0; i < size; i++)
{
    sum += arr[i];
}

// 指针算术访问
for (int *p = arr; p < arr + size; p++)
{
    sum += *p;
}

6.2 缓存友好的数据结构和算法

缓存友好的代码可以显著提高程序性能。

6.2.1 空间局部性

空间局部性是指程序倾向于访问最近访问过的内存位置附近的内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 缓存友好：按行访问
for (int i = 0; i < rows; i++)
{
    for (int j = 0; j < cols; j++)
    {
        sum += matrix[i][j];
    }
}

// 缓存不友好：按列访问
for (int j = 0; j < cols; j++)
{
    for (int i = 0; i < rows; i++)
    {
        sum += matrix[i][j];
    }
}

6.2.2 时间局部性

时间局部性是指程序倾向于多次访问同一内存位置。

1
2
3
4
5
6
7
8
9
10
11
12
// 时间局部性好：重复使用变量
int value = arr[i];
for (int j = 0; j < 10; j++)
{
    sum += value * j;
}

// 时间局部性差：重复访问数组元素
for (int j = 0; j < 10; j++)
{
    sum += arr[i] * j;
}

6.3 内存访问模式的优化

  • 减少内存访问次数：将频繁访问的数据存储在寄存器或局部变量中
  • 使用连续内存：使用数组而非链表，提高空间局部性
  • 避免内存碎片：合理规划内存分配，避免频繁分配和释放小内存
  • 内存对齐：合理安排数据结构，提高内存访问效率

7. 常见错误和调试

7.1 数组越界

数组越界是最常见的错误之一，可能导致程序崩溃或安全漏洞。

1
2
3
4
5
6
// 错误：数组越界
int numbers[5];
for (int i = 0; i <= 5; i++)  // 循环条件错误，应使用 i < 5
{
    numbers[i] = i;
}

7.2 野指针和悬垂指针

野指针和悬垂指针可能导致程序崩溃或未定义行为。

1
2
3
4
5
6
7
8
// 错误：未初始化的指针
int *p;
*p = 10;  // 野指针

// 错误：悬垂指针
int *p = (int *)malloc(sizeof(int));
free(p);
*p = 10;  // 悬垂指针

7.3 内存泄漏

内存泄漏会导致程序内存使用量不断增加，最终可能导致程序崩溃。

1
2
3
4
5
6
// 错误：内存泄漏
void function(void)
{
    int *p = (int *)malloc(100 * sizeof(int));
    // 没有调用 free(p);
}

7.4 调试技巧

  • 使用断言：在关键位置添加断言，检查指针是否为空、数组下标是否越界等
  • 使用内存调试工具：如 Valgrind、AddressSanitizer 等工具检测内存错误
  • 打印调试信息：在关键位置打印指针值、数组下标等信息
  • 代码审查：仔细检查内存分配和释放的配对情况

8. 示例：数组和指针的高级应用

8.1 示例 1：二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>

int binary_search(int arr[], int size, int target)
{
    int left = 0;
    int right = size - 1;
    
    while (left <= right)
    {
        int mid = left + (right - left) / 2;  // 避免整数溢出
        
        if (arr[mid] == target)
        {
            return mid;  // 找到目标，返回索引
        }
        else if (arr[mid] < target)
        {
            left = mid + 1;  // 目标在右半部分
        }
        else
        {
            right = mid - 1;  // 目标在左半部分
        }
    }
    
    return -1;  // 未找到目标
}

int main(void)
{
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    
    int result = binary_search(arr, size, target);
    
    if (result != -1)
    {
        printf("目标 %d 在索引 %d 处找到\n", target, result);
    }
    else
    {
        printf("目标 %d 未找到\n", target);
    }
    
    return 0;
}

8.2 示例 2：字符串反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include <string.h>

void reverse_string(char *str)
{
    if (str == NULL)
    {
        return;
    }
    
    int length = strlen(str);
    char *start = str;
    char *end = str + length - 1;
    
    while (start < end)
    {
        // 交换字符
        char temp = *start;
        *start = *end;
        *end = temp;
        
        // 移动指针
        start++;
        end--;
    }
}

int main(void)
{
    char str[] = "Hello, World!";
    printf("原字符串：%s\n", str);
    
    reverse_string(str);
    printf("反转后：%s\n", str);
    
    return 0;
}

8.3 示例 3：动态内存分配的矩阵运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h>
#include <stdlib.h>

// 分配矩阵
int **allocate_matrix(int rows, int cols)
{
    int **matrix = (int **)malloc(rows * sizeof(int *));
    if (matrix == NULL)
    {
        return NULL;
    }
    
    for (int i = 0; i < rows; i++)
    {
        matrix[i] = (int *)malloc(cols * sizeof(int));
        if (matrix[i] == NULL)
        {
            // 释放已分配的内存
            for (int j = 0; j < i; j++)
            {
                free(matrix[j]);
            }
            free(matrix);
            return NULL;
        }
    }
    
    return matrix;
}

// 释放矩阵
void free_matrix(int **matrix, int rows)
{
    if (matrix != NULL)
    {
        for (int i = 0; i < rows; i++)
        {
            free(matrix[i]);
        }
        free(matrix);
    }
}

// 打印矩阵
void print_matrix(int **matrix, int rows, int cols)
{
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

// 矩阵加法
int **add_matrices(int **a, int **b, int rows, int cols)
{
    int **result = allocate_matrix(rows, cols);
    if (result == NULL)
    {
        return NULL;
    }
    
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            result[i][j] = a[i][j] + b[i][j];
        }
    }
    
    return result;
}

int main(void)
{
    int rows = 2, cols = 3;
    
    // 分配矩阵
    int **a = allocate_matrix(rows, cols);
    int **b = allocate_matrix(rows, cols);
    
    if (a == NULL || b == NULL)
    {
        printf("内存分配失败\n");
        free_matrix(a, rows);
        free_matrix(b, rows);
        return 1;
    }
    
    // 初始化矩阵
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            a[i][j] = i * cols + j;
            b[i][j] = 10 + i * cols + j;
        }
    }
    
    // 打印矩阵
    printf("矩阵 A：\n");
    print_matrix(a, rows, cols);
    
    printf("矩阵 B：\n");
    print_matrix(b, rows, cols);
    
    // 矩阵加法
    int **c = add_matrices(a, b, rows, cols);
    if (c == NULL)
    {
        printf("内存分配失败\n");
        free_matrix(a, rows);
        free_matrix(b, rows);
        return 1;
    }
    
    printf("矩阵 C = A + B：\n");
    print_matrix(c, rows, cols);
    
    // 释放内存
    free_matrix(a, rows);
    free_matrix(b, rows);
    free_matrix(c, rows);
    
    return 0;
}

9. 小结

本章深入介绍了 C 语言中数组和指针的概念、使用方法和高级应用。数组和指针是 C 语言的核心概念，掌握它们对于理解 C 语言的工作原理和编写高效的 C 程序至关重要。

9.1 关键知识点

  • 数组：连续存储的相同类型元素的集合，大小固定，零基索引
  • 指针：存储内存地址的变量，支持算术运算和解引用
  • 数组和指针的关系：数组名是指向数组第一个元素的常量指针，数组下标访问等同于指针算术
  • 动态内存管理：使用 malloc、calloc、realloc 和 free 进行内存的分配和释放
  • 高级应用：动态数组、指针数组、函数指针、回调函数等
  • 性能优化：缓存友好的数据结构和算法，内存访问模式的优化
  • 常见错误：数组越界、野指针、悬垂指针、内存泄漏等

9.2 学习建议

  • 多写代码：通过实际编程练习掌握数组和指针的使用
  • 深入理解：理解数组和指针的内存布局和工作原理
  • 注意安全：始终检查指针是否为空，避免数组越界，正确管理内存
  • 学习调试：掌握使用调试工具检测和修复内存错误的技巧
  • 阅读优秀代码：学习开源项目中数组和指针的使用技巧

数组和指针是 C 语言的强大特性，也是 C 语言的难点所在。通过本章的学习，希望读者能够深入理解数组和指针的概念，掌握它们的使用方法，编写更加高效、安全的 C 程序。

在后续章节中，我们将学习字符串处理、结构体和共用体等复合数据类型，这些内容都与数组和指针密切相关。