cfla's blog

动态数组,二维数组,指针

发表于 更新于 分类于 阅读次数： Valine：

动态数组、二维数组、指针

本文会讲：

  • 二维数组的存储形式
  • 数组类型为什么会退化？
  • 二维数组的动态分配

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
#include <stdio.h>

int main(void)
{
    int a[4][2];

    // 初始化
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 2; j++)
            a[i][j] = i * 10 + j;

    printf("sizeof(int):\t%llu\n", sizeof(int));
    printf("sizeof(a):\t%llu\n", sizeof(a));
    printf("sizeof(a[0]):\t%llu\n", sizeof(a[0]));

    printf("\n");

    printf("a:\t%p\n", a);
    printf("&a:\t%p\n", &a);
    printf("\n");

    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 2; j++)
            printf("a[%d][%d]:\t%02d\n", i, j, a[i][j]);

    printf("\n");

    for (int i = 0; i < 4; i++)
        printf("a[%d]:\t%p\n", i, a[i]);

    printf("\n");

    for (int i = 0; i < 4; i++)
        printf("*a[%d]:\t%d\n", i, *a[i]);

    printf("\n");

    for (int i = 0; i < 4; i++)
        printf("&a[%d]:\t%p\n", i, &a[i]);

    printf("\n");

    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 2; j++)
            printf("&a[%d][%d]:\t%p\n", i, j, &a[i][j]);
    
    return 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
sizeof(int):    4
sizeof(a):      32      
sizeof(a[0]):   8       

a:      000000000064FDD0
&a:     000000000064FDD0

a[0][0]:        00
a[0][1]:        01
a[1][0]:        10
a[1][1]:        11
a[2][0]:        20
a[2][1]:        21
a[3][0]:        30
a[3][1]:        31

a[0]:   000000000064FDD0
a[1]:   000000000064FDD8
a[2]:   000000000064FDE0
a[3]:   000000000064FDE8

*a[0]:  0
*a[1]:  10
*a[2]:  20
*a[3]:  30

&a[0]:  000000000064FDD0
&a[1]:  000000000064FDD8
&a[2]:  000000000064FDE0
&a[3]:  000000000064FDE8

&a[0][0]:       000000000064FDD0
&a[0][1]:       000000000064FDD4
&a[1][0]:       000000000064FDD8
&a[1][1]:       000000000064FDDC
&a[2][0]:       000000000064FDE0
&a[2][1]:       000000000064FDE4
&a[3][0]:       000000000064FDE8
&a[3][1]:       000000000064FDEC

可以看出，二维数组是连续储存的，有&a = a = &a[0] = a[0] = &a[0][0] ，以此类推。

我们可以这样表示二维数组

a
a[0] a[1] a[2] a[3]
a[0] [0] a[0] [1] a[1] [0] a[1] [1] a[2] [0] a[2] [1] a[3] [0] a[3] [1]

2 数组类型为什么会退化？

有的时候会出现这种情况：

在主函数里声明了一个二维数组，使用sizeof 会得到它的大小，但传到函数里，却只能得到指针的大小，这是为什么呢？

详见：https://www.zhihu.com/question/464844221/answer/1940453834

3 动态分配二维数组

3.1 第一种方法

先申请一维数组，在将该一维数组强制转换成二维数组

前置知识：

一维数组的数组名是：一个指向数据类型的指针，如int *，初次之外没有任何多余的信息

二维数组的数组名是：一个【指向一维数组的指针】，在这里，一维数组就相当于数据类型，

即int q[][4] 和int (*q)[4] 是等价的，两者都是指向一维数组的指针，当对这个指针 + 2时，就等价于q += 2 * 4 * sizeof(int)

直接贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int *a = (int *)malloc(2 * 4 * sizeof(int));
    for (int i = 0; i < 8; i++)
        a[i] = i;
    int (*b)[4] = (int (*)[4])a;
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 4; j++)
            printf("%d ", b[i][j]);
        printf("\n");
    }
    return 0;
}

我们首先创建了一个一维数组，这个数组存储了8个连续的整数类型。

我们用int (*b)[4] 声明了一个指向 四个元素的数组 的指针。

然后对数组a进行强制类型转换，将它转换成了一个指向4个元素数组的指针。

这样动态分配的指针和直接int b[2][4] 是一样的。

下面我们使用 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
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    // 初始化数组
    int *b = (int *)malloc(2 * 4 * sizeof(int));
    for (int i = 0; i < 8; i++)
        b[i] = i;
    int (*a)[2] = (int (*)[2])b;

    printf("sizeof(int):\t%llu\n", sizeof(int));
    printf("sizeof(a):\t%llu\n", sizeof(a));
    printf("sizeof(a[0]):\t%llu\n", sizeof(a[0]));

    printf("\n");

    printf("a:\t%p\n", a);
    printf("&a:\t%p\n", &a);
    printf("\n");

    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 2; j++)
            printf("a[%d][%d]:\t%02d\n", i, j, a[i][j]);

    printf("\n");

    for (int i = 0; i < 4; i++)
        printf("a[%d]:\t%p\n", i, a[i]);

    printf("\n");

    for (int i = 0; i < 4; i++)
        printf("*a[%d]:\t%d\n", i, *a[i]);

    printf("\n");

    for (int i = 0; i < 4; i++)
        printf("&a[%d]:\t%p\n", i, &a[i]);

    printf("\n");

    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 2; j++)
            printf("&a[%d][%d]:\t%p\n", i, j, &a[i][j]);
}

运行结果如下

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
sizeof(int):    4
sizeof(a):      8       
sizeof(a[0]):   8       

a:      00000000009C1420
&a:     000000000064FDF0

a[0][0]:        00      
a[0][1]:        01      
a[1][0]:        02
a[1][1]:        03
a[2][0]:        04
a[2][1]:        05
a[3][0]:        06
a[3][1]:        07

a[0]:   00000000009C1420
a[1]:   00000000009C1428
a[2]:   00000000009C1430
a[3]:   00000000009C1438

*a[0]:  0
*a[1]:  2
*a[2]:  4
*a[3]:  6

&a[0]:  00000000009C1420
&a[1]:  00000000009C1428
&a[2]:  00000000009C1430
&a[3]:  00000000009C1438

&a[0][0]:       00000000009C1420
&a[0][1]:       00000000009C1424
&a[1][0]:       00000000009C1428
&a[1][1]:       00000000009C142C
&a[2][0]:       00000000009C1430
&a[2][1]:       00000000009C1434
&a[3][0]:       00000000009C1438
&a[3][1]:       00000000009C143C

可以看到除了小部分细节（sizeof(a) 、&a）与我们直接声明二维数组表现得不一样，其他的行为与直接声明二维数组是一模一样的。

这种方法得到的二维数组虽然和原生的二维数组一样，但它也有缺点，就是它不能动态分配行的长度，即列的大小。因此只能说是半个动态数组。而且，更令人烦恼的是，指向数组的指针，int (*)[len] 这个类型也无法作为函数的返回值，或者使用typedef来取别名，不方便我们对它进行包装。

3.2 第二种方法：

参考: https://blog.csdn.net/morewindows/article/details/7664479# 我这里将原文的int 替换成了size_t

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
//C语言中动态的申请二维数组 malloc free
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//动态申请二维数组
template <typename T>
T** malloc_Array2D(int row, int col)
{
  int size = sizeof(T);
  int point_size = sizeof(T*);
  //先申请内存，其中point_size * row表示存放row个行指针
  T **arr = (T **) malloc(point_size * row + size * row * col);
  if (arr != NULL)
  {	
    memset(arr, 0, point_size * row + size * row * col);
    T *head = (T*)((size_t)arr + point_size * row);    // 这里将arr转换成int型是为了直接进行算数相加，但我觉得还是转换成size_t好
    while (row--)
      arr[row] = (T*)((size_t)head + row * col * size);
  }
  return (T**)arr;
}

//释放二维数组
void free_Aarray2D(void **arr)
{
  if (arr != NULL)
    free(arr);
}
int main()
{
  printf("  C语言中动态的申请二维数组 malloc free\n");  
  printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");
 
  printf("请输入行列(以空格分开): ");
  int nRow, nCol;
  scanf("%d %d", &nRow, &nCol);
 
  //动态申请连续的二维数组
  int **p = malloc_Array2D<int>(nRow, nCol);
 
  //为二维数组赋值	
  int i, j;	
  for (i = 0; i < nRow; i++)
    for (j = 0; j < nCol; j++)
      p[i][j] = i + j;
 
  //输出二维数组	
  for (i = 0; i < nRow; i++)
  {
    for (j = 0; j < nCol; j++)
      printf("%4d ", p[i][j]);
    putchar('\n');
  }
 
  free_Aarray2D((void**)p);
  return 0;
}

这里，原作者对指针的操作让我叹为观止。

但是，用这种方法创作出来的二维数组和直接int b[2][4] 得到的二维数组，结构显然是不一样的，这里我们不在进行仔细地检查。

它的具体结构我将在下一小节介绍

3.3 第三种方法

参考：https://blog.csdn.net/houqd2012/article/details/8146070

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
#include <stdio.h>
#include <stdlib.h>

int **make_array2D(int row, int col)
{
    int **arr = (int **)malloc(row * sizeof(int *));
    arr[0] = (int *)malloc(row * col * sizeof(int));
    for (int i = 1; i < row; i++)
        arr[i] = arr[i - 1] + col;
    return arr;
}

void free_array2D(int **arr)
{
    free(arr[0]);
    free(arr);
}

int main(void)
{
    int **a = make_array2D(2, 4);
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 4; j++)
            a[i][j] = 10 * i + j;

    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 4; j++)
            printf("%d ", a[i][j]);
        printf("\n");
    }
    free_array2D(a);
    return 0;
}

乍一看，这种方法生成地数组，其地址是连续地，应该和原生的二维数组是一样的(包括这种方法的原作者也是这样认为的)，但如果我们仔细检查，我们会发现它其实和原生的二维数组是不一样的。

我们使用 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
#include <stdio.h>
#include <stdlib.h>

int **make_array2D(int row, int col)
{
    int **arr = (int **)malloc(row * sizeof(int *));
    arr[0] = (int *)malloc(row * col * sizeof(int));
    for (int i = 1; i < row; i++)
        arr[i] = arr[i - 1] + col;
    return arr;
}

void free_array2D(int **arr)
{
    free(arr[0]);
    free(arr);
}

int main(void)
{
    int **a = make_array2D(4, 2);
    
    // 初始化
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 2; j++)
            a[i][j] = 10 * i + j;

    printf("sizeof(int):\t%llu\n", sizeof(int));
    printf("sizeof(a):\t%llu\n", sizeof(a));
    printf("sizeof(a[0]):\t%llu\n", sizeof(a[0]));

    printf("\n");

    printf("a:\t%p\n", a);
    printf("&a:\t%p\n", &a);
    printf("\n");

    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 2; j++)
            printf("a[%d][%d]:\t%02d\n", i, j, a[i][j]);

    printf("\n");

    for (int i = 0; i < 4; i++)
        printf("a[%d]:\t%p\n", i, a[i]);

    printf("\n");

    for (int i = 0; i < 4; i++)
        printf("*a[%d]:\t%d\n", i, *a[i]);

    printf("\n");

    for (int i = 0; i < 4; i++)
        printf("&a[%d]:\t%p\n", i, &a[i]);

    printf("\n");

    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 2; j++)
            printf("&a[%d][%d]:\t%p\n", i, j, &a[i][j]);
    free_array2D(a);
    return 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
sizeof(int):    4
sizeof(a):      8
sizeof(a[0]):   8

a:      0000000000701420
&a:     000000000064FDF0

a[0][0]:        00
a[0][1]:        01
a[1][0]:        10
a[1][1]:        11
a[2][0]:        20
a[2][1]:        21
a[3][0]:        30
a[3][1]:        31

a[0]:   0000000000701450
a[1]:   0000000000701458
a[2]:   0000000000701460
a[3]:   0000000000701468

*a[0]:  0
*a[1]:  10
*a[2]:  20
*a[3]:  30

&a[0]:  0000000000701420
&a[1]:  0000000000701428
&a[2]:  0000000000701430
&a[3]:  0000000000701438

&a[0][0]:       0000000000701450
&a[0][1]:       0000000000701454
&a[1][0]:       0000000000701458
&a[1][1]:       000000000070145C
&a[2][0]:       0000000000701460
&a[2][1]:       0000000000701464
&a[3][0]:       0000000000701468
&a[3][1]:       000000000070146C

从上面的结果可以看出，这种方法生成的二维数组，虽然地址是连续的，但它的结构和直接int b[2][4] 得到的二维数组，还是不一样的。

它的具体结构我将在下一小节介绍

3.4 总结 ： 下标运算符

首先我们介绍下标运算符，上面的三种动态分配二维数组的方法，其原理都是基于下标运算符。

下标运算符是左结合的，我们引用二维数组，通常是这样的 arr[i][j] 但其实也可以这样 (arr[i])[j] 这两种形式是等价的。

下面我们详细地描述下标运算符

ElementType[i] = *((size_t)ElementType + i * sizeof(ElementType))

可见下标运算符最重要的就是ElementType，这个ElementType 可以是内置类型 int，可以是指针类型int **, 也可以是数组类型 int (*)[]，在使用下标运算符时，我们要尤其注意ElementType，尤其是在我们接下来分析二维数组时。

首先我们来看内置的数组类型

a
a[0] a[1] a[2] a[3]
a[0] [0] a[0] [1] a[1] [0] a[1] [1] a[2] [0] a[2] [1] a[3] [0] a[3] [1]

一个内置数组类型表示为int a[5][5] ，但拎出来a，他的类型是 int (*)[5] 所以arr[1] 其实是指a[1][0] 这个位置。a[1] 的类型是int * 所以(a[1])[1] 的类型就是int

接下来我们看动态分配二维数组的第一种方法：

这种方法一开始申请了一个一维数组int *a = (int *)malloc(2 * 4 * sizeof(int)) a的类型是int *

接下来我们使用强制类型转换，将a由int * 转换为int (*)[4] ，这样它就和内置的二维数组一样了。也可以使用两个下标运算符进行访问。

接下类我们看动态分配二维数组的第二种方法：

首先我们将这种方法分配的图画出来

image-20220906194800829

设行数为row，列数为col，假设二维数组存储的类型为 int

第二种方法申请了 row * sizeof(int *) + row * col * sizeof(int) 字节的空间。

这个表达式的前一项row * sizeof(int *) 代表a[0] a[1] a[2] 的空间，后一项row * col * sizeof(int) 指的是连续的二维数组的存储空间。

这个程序做的就是让a[0]指向a[0] [0]，让a[1] 指向 a[1] [0]，依此类推。

需要注意的是这个二维数组的类型，虽然这个二维数组可以使用两个下标运算符引用，但原理却和内置的二维数组完全不同。第二种二维数组的类型是int ** 而不是int (*)[col] ，也决不能是int (*)[col] 。要理解这个，我们看一下在使用下标运算符时究竟发生了什么？

首先a的类型时int ** ，a[1]，代表a之后一个指针大小位置的内容，即

*((size_t)a + 1 * sizeof(int *))，就是a[1] [0]的地址，而(a[1])[0] 就是a[1] [0]的内容。

为了保证我们第一个下表运算符能够得到a[1] [0] 的地址，我们必须保证这个二维数组的类型是int **

第三种二维数组的分析与第二种类似，这里我们给出它的表示

image-20220906200208361

4 指针

我们使用一个程序来展示 int (*)[col] 类型

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
#include <stdio.h>

void func_1(int a[][8], int n)
{
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < 8; j++)
      printf("%d ", a[i][j]);
    printf("\n");
  }
}

void func_2(int (*a)[8], int n)
{
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < 8; j++)
      printf("%d ", a[i][j]);
    printf("\n");
  }
}

void func_3(int (*a)[8])  // 指向数组的指针
{
  for (int i = 0; i < 8; i++)
    printf("%d ", (*a)[i]);
}

int main(void)
{
  int q[4][8];
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 8; j++)
      q[i][j] = 10 * i + j;

  func_1(q, 4);
  printf("\n");
  func_2(q, 4);
  printf("\n");

  int p[8] = {0, 1, 2, 3, 4, 5, 6, 7};
  func_3(&p);		// 因为是指向数组的指针，p必须要取地址
}

贴一篇文章 ：https://blog.csdn.net/soonfly/article/details/51131141

这篇文章里对指针类型的分析很好

1
2
3
4
5
6
7
8
9
int p; //这是一个普通的整型变量
int *p; //首先从P 处开始,先与*结合,所以说明P 是一个指针,然后再与int 结合,说明指针所指向的内容的类型为int 型.所以P是一个返回整型数据的指针
int p[3]; //首先从P 处开始,先与[]结合,说明P 是一个数组,然后与int 结合,说明数组里的元素是整型的,所以P 是一个由整型数据组成的数组
int *p[3]; //首先从P 处开始,先与[]结合,因为其优先级比*高,所以P 是一个数组,然后再与*结合,说明数组里的元素是指针类型,然后再与int 结合,说明指针所指向的内容的类型是整型的,所以P 是一个由返回整型数据的指针所组成的数组
int (*p)[3]; //首先从P 处开始,先与*结合,说明P 是一个指针然后再与[]结合(与"()"这步可以忽略,只是为了改变优先级),说明指针所指向的内容是一个数组,然后再与int 结合,说明数组里的元素是整型的.所以P 是一个指向由整型数据组成的数组的指针
int **p; //首先从P 开始,先与*结合,说是P 是一个指针,然后再与*结合,说明指针所指向的元素是指针,然后再与int 结合,说明该指针所指向的元素是整型数据.由于二级指针以及更高级的指针极少用在复杂的类型中,所以后面更复杂的类型我们就不考虑多级指针了,最多只考虑一级指针.
int p(int); //从P 处起,先与()结合,说明P 是一个函数,然后进入()里分析,说明该函数有一个整型变量的参数,然后再与外面的int 结合,说明函数的返回值是一个整型数据
Int (*p)(int); //从P 处开始,先与指针结合,说明P 是一个指针,然后与()结合,说明指针指向的是一个函数,然后再与()里的int 结合,说明函数有一个int 型的参数,再与最外层的int 结合,说明函数的返回类型是整型,所以P 是一个指向有一个整型参数且返回类型为整型的函数的指针
int *(*p(int))[3]; //可以先跳过,不看这个类型,过于复杂从P 开始,先与()结合,说明P 是一个函数,然后进入()里面,与int 结合,说明函数有一个整型变量参数,然后再与外面的*结合,说明函数返回的是一个指针,,然后到最外面一层,先与[]结合,说明返回的指针指向的是一个数组,然后再与*结合,说明数组里的元素是指针,然后再与int 结合,说明指针指向的内容是整型数据.所以P 是一个参数为一个整数据且返回一个指向由整型指针变量组成的数组的指针变量的函数.