取得动态二维数组

深藏阁楼爱情的钟 2022-08-04 04:03 153阅读 0赞

在C语言中，有内置的一维数组，二维数组等多维数组，也可以使用动态分配内存的方式，很容易的得到一个

类似内置静态一维数组的动态数组（在这里我这么叫，也许并不存在这个定义 :)），但如何取得动态的二维

数据组呢？如果理解了C语言中对于数组指针的访问方式，那么实现一个自己的二维数组是很简单的。

下面首先理清一下一维数据指针的访问方式：

假设定义有如下定义:

\#define DIMS 10

int Arr1\[DIMS\]

int \*pArr1;

学过C语言的人都知道可以如下访问数据中的每一个元素：

Arr1\[i\] = xxxx;

同样理解数据即指针也可以知道：

pArr1 = Arr1;

for (int i = 0; i < DIMS; ++i)

\*pArr1 = xxxx;

pArr1++;

这是一维的情况，那么二维呢？

对于静态的二维数组，三维数组等等都是很方便的

int Arr2\[DIMS\]\[DIMS\];

int \*pArr2;

for (int i = 0; i < DIMS; ++i)

for (int j = 0; j < DIMS; ++j)

Arr2\[i\]\[j\] = xxxx; //访问数组单元

pArr2 = Arr2;

for (int i = 0; i < DIMS \* DIMS; ++i)

\*pArr2++ = xxxx; //访问数组单元,并下移指针

三维方式差不多，在C语言中，静态多维数据其实就是一个平面数据，C语言编译器会将数据访问的形式翻译成

内存访问的形式。

比如：

一维： Arr1\[i\]   ----> \*(Arr1 + (i \* sizeof(Arr1\[0\])))

二维： Arr2\[i\]\[j\] ---> \*(Arr2 + (i \* sizeof(Arr2\[0\]\[0\]) + n \* sizeof(Arr2\[0\]\[0\]))  
       这里的n是二维数据的第二个下标的最大值

三维：方式与上类似，以数组首地址开始，计算数据偏移。  
使用下标使用数组的方式，给人以清晰的感觉，两样可以增加写程序的复杂度，意味着可以减少错误的机率。  
在一些情况下，使用静态的二维数据有着它的局限性，在大小未知的情况下，使用静态数组就不方便，有某些

情况下，会很耗费栈资源（静态数组在栈中分配），所以需要动态数组。对于一维的情况，可以像一维静态数

据那样使用，可是对于多维数组，如果只是像静态数组那样分配元素所需要的空间，那么就无法使用下标方式

访问数据。  
int \*pArr1, \*\*pArr2;  
pArr1 = (int\*)malloc(sizeof(int) \* DIMS);  
pArr2 = (int\*\*)malloc(sizeof(int) \* DIMS \* DIMS);  
...  
pArr1\[i\] = xxx;  //正确  
pArr2\[i\]\[j\] = xxx; //错误

这里二维为什么有问题呢？  
看一下反汇编指命：  
65:       pArr2\[4\]\[5\] = 10;  
004011B8   mov         eax,dword ptr \[ebp-4\]  ;ebp-4是变量int \*\*pArr2  
004011BB   mov         ecx,dword ptr \[eax+10h\]  ;10h = 4 \* sizeof(int) = 4 \* 4  
004011BE   mov         dword ptr \[ecx+14h\],0Ah  ;14h = 5 \* 4  
这三行汇编指命是在VC6.0下生成的。  
第一行将变量地址存入EAX，然后将EAX移动到第四个偏移移到ECX，然后再取得第5个位置的数据，实现上这里

可以如下解析：  
(pArr2\[4\])\[5\]  
下面来看一下静态二维数据的汇编代码：  
64:       Arr2\[4\]\[5\] = 10;  
004011AE   mov         dword ptr \[ebp-0DCh\],0Ah  ;0DCh = \[(10-1) - 4\]\*40 + (5-1)\*4 - 4  
与上面相比，这里的方式有着很大的不同。静态二维数据是直接访问的，而动态方式，C语言并不认为是数组

，而是将其看成二次间接。  
有了以上的基础之后，我想读者一定很快就知道如何去实现一个动态二维数据了。  
首先建立一个行指针，指针行的数据，然后将行指针返回作为二维数据指针就OK了。  
下面给出示意图：

![简明实现动态二维指针][Figure1.JPG]

这样就有一个问题，为申请一个二维数组，需要分配多次空间，这样会产生内存碎片，如是我想到了一种一次

性分配内存的方法。示意图如下：

![一次性分配二维数组内存示意图][Figure2.JPG]  
最终实现代码如下：  
Dyn2DimArr.h  
\-------------------------  
\#ifndef \_\_DYN2DIMARR\_HEADER\_H\_\_ \#define \_\_DYN2DIMARR\_HEADER\_H\_\_ /\*\* \* 取得一个动态二维数组,可以使用\[i\]\[j\]方式访问 \* 返回一个二维数据指针 \*/ void\*\* GetDyn2DimArr(int m, int n, int element\_size); /\*\* \* 释放二维数据内存 \*/ void FreeDyn2DimArr(void \*\*pArr2); \#endif //~\_\_DYN2DIMARR\_HEADER\_H\_\_

Dyn2DimArr.c  
\-------------------------  
\#include <stdlib.h> \#include <string.h> \#include <assert.h> \#include "Dyn2DimArr.h" void\*\* GetDyn2DimArr(int m, int n, int element\_size) \{ void \*pMem = NULL; void \*\*pMemOwner = NULL; int pt\_size; int user\_size, owner\_size, line\_size; int i; assert(m > 0 && n > 0); assert(element\_size > 0); line\_size = n \* element\_size; user\_size = m \* line\_size; pt\_size = sizeof(void\*); owner\_size = pt\_size \* m; pMem = malloc(user\_size + owner\_size); if(pMem == NULL) return NULL; memset(pMem, 0, user\_size + owner\_size); // 在这里转化成void\*\*是有意义的,因为在ANSI C语言中不能实现void\*的 // 的运算,尽管在GNU C中是可以的,但也是以char\*作为运算尺寸的 // 转化成void\*\*就相当于对一个指针的指针运算,也就是偏移一个位置就是 // 一个指针的大小,在这里不能假设大小为4,因为在64位平台,指针大小为8 pMemOwner = (void\*\*)pMem + user\_size / pt\_size; for (i = 0; i < m; ++i) \{ pMemOwner\[i\] = (void\*\*)pMem + (i \* line\_size / pt\_size); \} return pMemOwner; \} void FreeDyn2DimArr(void \*\*pArr2) \{ // 实现自己的内存释放是有好处的,如果以后内在分配是采用其它分配方式 // 可以不用修改客户代码,同样也可以避免客户知道其就是一个一维指针. free(pArr2\[0\]); \}

好了，二维动态数组已经实现了，会不会有人问三维的呢？我想实现原理已经在这里，问题应该不大了吧。

为了方便使用，这里贴出测试代码，以可以使用的方式。

\#include <stdio.h> \#include <stdlib.h> \#include "Dyn2DimArr.h" int main(int argc, char \*\*argv) \{ int \*\*Arr2; int \*ArrLine; int \*pData; int i, j; Arr2 = (int\*\*)GetDyn2DimArr(8, 10, sizeof(int)); for (i = 0; i < 8; ++i)\{ for (j = 0; j < 10; ++j)\{ Arr2\[i\]\[j\] = i << 8 | j; \} \} printf("使用Arr2\[i\]\[j\]方式/n"); for (i = 0; i < 8; ++i)\{ for (j = 0; j < 10; ++j)\{ printf("(%d,%d) ", Arr2\[i\]\[j\] >> 8, Arr2\[i\]\[j\] & 0xFF); \} printf("/n"); \} printf("/n"); printf("使用Arr2\[i\]取得行指针ArrLine,再使用ArrLine\[j\]方式/n"); for (i = 0; i < 8; ++i)\{ ArrLine = Arr2\[i\]; for (j = 0; j < 10; ++j)\{ printf("(%d,%d) ", ArrLine\[j\] >> 8, ArrLine\[j\] & 0xFF); \} printf("/n"); \} printf("/n"); printf("使用Arr2\[i\]取得行指针ArrLine,再使用\*ArrLine+偏移方式/n"); for (i = 0; i < 8; ++i)\{ ArrLine = Arr2\[i\]; for (j = 0; j < 10; ++j)\{ printf("(%d,%d) ", \*ArrLine >> 8, \*ArrLine & 0xFF); ++ArrLine; \} printf("/n"); \} printf("/n"); printf("使用Arr2\[0\]取得数据指针,直接使用全偏移方式访问所有数据/n"); pData = Arr2\[0\]; //这里不能直接使用Arr2,这是与静态二维数组不同的地方 for (i = 0; i < 8; ++i)\{ for (j = 0; j < 10; ++j)\{ printf("(%d,%d) ", \*pData >> 8, \*pData & 0xFF); ++pData; \} printf("/n"); \} FreeDyn2DimArr(Arr2); Arr2 = NULL; return 0; \}

[Figure1.JPG]: /images/20220731/2e21ce3d3e0c426cb82b8c27b8549d42.png
[Figure2.JPG]: /images/20220731/475155269e314f13b1f9bc41ba5f4551.png