8.5 多维数组

前几节讲述了一维数组的各种展示形态,而超过一维的多维数组在内存中如何存储呢?内存中数据是线性排列的。多维数组看上去像是在内存使用了多块空间来存储数据,事实是这样的吗?编译器采用了非常简单有效的手法,将多维数组通过转化重新变为一维数组。在本节中,多维数组的讲解以二维数组为例,如二维整型数组:int nArray[2][2],经过转换后可用一维数组表示为:int nArray[4]。它们在内存中的存储方式也相同,如图8-9所示。

图 8-9 一维数组与二维数组内存对比

两者在内存中的排列相同,可见在内存中根本就没有多维数组。二维数组甚至多维数组的出现只是为了方便开发者计算偏移地址、寻址数组数据。

二维数组的大小计算非常简单,一维数组使用类型大小乘以下标值,得到一维数组占用内存大小。二维数组中的二维下标值为一维数组个数,因此只要将二维下标值乘以一维数组占用内存大小,即可得知二维数组的大小。

求得二维数组的大小后,它的地址偏移如何计算呢?根据之前的学习,我们知道一维数组的寻址根据“数组首地址+类型大小*下标值”。计算二维数组的地址偏移要先分析二维数组的组成部分,如整型二维数组int nArray[2][3]可拆分为三部分:

数组首地址:nArray

一维元素类型:int[3],此下标值记作j

类型:int

元素个数:[3]

一维元素个数:[2],此下标值记作i

此二维数组的组成可理解为两个一维整型数组的集合,而这两个一维数组又各自拥有三个整型数据。在地址偏移的计算过程中,先计算出首地址到一维数组间的偏移量,利用数组首地址加上偏移量,得到某个一维数组所在地址。以此地址作为基地址,加上一维数组中数据地址偏移,寻址到二维数组中某个数据。其寻址公式为


数组首地址+sizeof(type[J])*二维下标值+sizeof(type)*一维下标值


二维以上数组的寻址同理。多维数组的组成可看做是一个包裹中套小包裹。如三维数组int nArray[2][3][4],最左侧的int nArray[2]为第一层包内数据,下标值2说明在第一层包裹中有两个二维数组int[3][4]小包裹。打开小包裹中的一个,里面包着一个一维数组int[4]。再次打开其中一个包裹,里面包含一个int数据。依照这个拆包过程,结合公式,就可以准确定位到多维数组的数据。

将理论与实践结合,分析代码清单8-10,进一步加强对多维数组的学习、理解。

代码清单8-10 二维数组与一维数组对比—Debug版


//C++源码说明:二维数组、一维数组寻址演示

void main(){

int i=0;

int j=0;

int nArray[4]={1,2,3,4};//一维数组

int nTwoArray[2][2]={{1,2},{3,4}};//二维数组

scanf("%d%d",&i,&j);

printf("nArray=%d\r\n",nArray[i]);

printf("nTwoArray=%d\r\n",nTwoArray[i][j]);

}

//C++源码与对应汇编代码讲解

void main(){

int i=0;

0040B878 mov dword ptr[ebp-4],0;局部变量赋值

int j=0;

0040B87F mov dword ptr[ebp-8],0;局部变量赋值

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

0040B886 mov dword ptr[ebp-18h],1;一维数组初始化

0040B88D mov dword ptr[ebp-14h],2

0040B894 mov dword ptr[ebp-10h],3

0040B89B mov dword ptr[ebp-0Ch],4

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

0040B8A2 mov dword ptr[ebp-28h],1;二维数组初始化

0040B8A9 mov dword ptr[ebp-24h],2;和一维数组没有任何区别

;从初始化反汇编代码中无法区分一维数组与二维数组

0040B8B0 mov dword ptr[ebp-20h],3

0040B8B7 mov dword ptr[ebp-1Ch],4

scanf("%d%d",&i,&j);

;scanf函数分析讲解略

printf("nArray=%d\r\n",nArray[i]);

0040B8D3 mov edx, dword ptr[ebp-4];获取下标值i并将其保存到edx中

;此处获取数组中数据的地址偏移,下标值i被保存在edx中,

;edx*4等同于公式中的sizeof(type)*下标值

;ebp-18h是数组nArray首地址,寻址到偏移地址处,取出其中数据,存入eax中保存

0040B8D6 mov eax, dword ptr[ebp+edx*4-18h]

0040B8DA push eax;用eax来保存寻址到的数据

0040B8DB push offset string"nArray=%d\r\n"(00420028)

0040B8E0 call printf(00401170)

0040B8E5 add esp,8

printf("nTwoArray=%d\r\n",nTwoArray[i][j]);

0040B8E8 mov ecx, dword ptr[ebp-4];获取下标值i并将其保存到ecx中

;同样是计算偏移,但这里获取的不是数据,而是地址值。与一维数组nArray有些类似

;同样是使用首地址加偏移,二维数组nTwoArray首地址为ebp-28h

;ecx*8为偏移,计算公式sizeof(int[2])*下标值

;得出一维数组首地址,将结果保存到edx

0040B8EB lea edx,[ebp+ecx*8-28h]

0040B8EF mov eax, dword ptr[ebp-8];获取下标值j并将其保存到eax中

;此处又回归到一维数组寻址,edx为数组首地址,eax*4为偏移计算

;sizeof(type)*下标值

0040B8F2 mov ecx, dword ptr[edx+eax*4]

0040B8F5 push ecx

0040B8F6 push offset string"nTwoArray=%d\r\n"(00420f8c)

0040B8FB call printf(00401170)

0040B900 add esp,8

}


代码清单8-10演示了一维数组与二维数组的寻址方式。二维数组的寻址过程比一维数组多一步操作,先取得二维数组中某个一维数组的首地址,再利用此地址作为基址寻址到一维数组中某个数据地址处。

在代码清单8-10的二维数组寻址过程中,两下标值都是未知变量,若其中某一下标值为常量,则不会出现二次寻址计算。二维数组寻址转换成汇编后的代码和一维数组相似。由于下标值为常量,且类型大小可预先计算出,因此变成两常量计算,利用常量折叠可直接计算出偏移地址。修改代码清单8-10中的二维数组寻址,将二维下标值改为常量1,如代码清单8-11所示。

代码清单8-11 使用常量寻址二维数组—Debug版


//C++源码说明:使用常量寻址二维数组

void main(){

int i=0;

int nTwoArray[2][2]={{1,2},{3,4}};//二维数组

scanf("%d",&i);

printf("nTwoArray=%d\r\n",nTwoArray[1][i]);

}

//C++源码与对应汇编代码讲解

void main(){

int i=0;

0040B878 mov dword ptr[ebp-4],0//初始化下标i

int nTwoArray[2][2]={{1,2},{3,4}};//数组初始化

0040B87F mov dword ptr[ebp-14h],1

0040B886 mov dword ptr[ebp-10h],2

0040B88D mov dword ptr[ebp-0Ch],3

0040B894 mov dword ptr[ebp-8],4

scanf("%d",&i);

;scanf分析略

printf("nTwoArray=%d\r\n",nTwoArray[1][i]);

0040B8AC mov ecx, dword ptr[ebp-4];取下标值i

;只使用了一次寻址,由于二维下标为1,直接计算出基地址为

;ebp-14h+sizeof(int[2])=ebp-14h+8h=ebp-0Ch

0040B8AF mov edx, dword ptr[ebp+ecx*4-0Ch]

0040B8B3 push edx

0040B8B4 push offset string"nTwoArray=%d\r\n"(00420f8c)

0040B8B9 call printf(00401170)

0040B8BE add esp,8

}


代码清单8-11中的二维数组常量折叠优化在一维数组中也会出现,当一维数组下标值为常量时,会直接计算出偏移量。

代码清单8-10使用O2选项进行优化后,数组中的各成员不会连续初始化,而是将一维数组与二维数组同步初始化,因为它们中的数据都是1、2、3、4,可使用公共表达式优化。使用O2选项重新编译代码清单8-10,分析优化后的数组初始化过程,以及在Release版下数组的寻址过程,如代码清单8-12所示。

代码清单8-12 一维数组、二维数组初始化及寻址优化—Release版


;int__cdecl main(int argc, const char**argv, const char**envp)

_main proc near

var_28=dword ptr-28h;局部变量标号定义,共10个局部变量

var_24=dword ptr-24h

var_20=dword ptr-20h

var_1C=dword ptr-1Ch

var_18=dword ptr-18h

var_14=dword ptr-14h

var_10=dword ptr-10h

var_C=dword ptr-0Ch

var_8=dword ptr-8

var_4=dword ptr-4

argc=dword ptr 4

argv=dword ptr 8

envp=dword ptr 0Ch

sub esp,28h;调整栈顶,开辟局部变量栈空间

xor eax, eax;清空eax

mov ecx,3;赋值ecx为3

mov[esp+28h+var_28],eax;赋值局部变量var_28为0

mov[esp+28h+var_24],eax;赋值局部变量var_24为0

mov eax,4;赋值eax为4

mov[esp+28h+var_18],ecx;赋值局部变量var_18为3

mov[esp+28h+var_14],eax;赋值局部变量var_14为4

mov[esp+28h+var_4],eax;赋值局部变量var_4为4

mov[esp+28h+var_8],ecx;赋值局部变量var_8为3

lea eax,[esp+28h+var_24];取出变量var_24地址存入eax

lea ecx,[esp+28h+var_28];取出变量var_28地址存入ecx

push eax;将eax压入栈中,作为_scanf函数参数

mov edx,2;赋值edx为2

push ecx;将ecx压入栈中,作为_scanf函数参数

push offset aDD;压入字符串"%d%d"

mov[esp+34h+var_20],1;赋值变量var_20为1

mov[esp+34h+var_1C],edx;赋值变量var_1C为2

mov[esp+34h+var_10],1;赋值变量var_10为1

mov[esp+34h+var_C],edx;赋值变量var_C为2

call_scanf;调用_scanf函数

;根据以上代码分析,得出两下标变量对应编号分别为:var_24、var_28

;两数组首地址对应编号为:var_20、var_10

mov edx,[esp+34h+var_28];使用edx保存下标变量var_28

;var_20为基址,edx为下标值,乘以类型大小4获取数据

;从寻址方式上看,这里是一维数组寻址,

;其数组类型为占4字节内存空间的数据,将得到的数据存入eax中

mov eax,[esp+edx*4+34h+var_20]

push eax;将eax作为_printf函数参数压入栈中

push offset Format;压入字符串"nArray=%d\r\n"

call_printf;调用函数_printf

mov ecx,[esp+3Ch+var_24];获取下标变量var_24,存入ecx中

mov edx,[esp+3Ch+var_28];获取下标变量var_28,存入edx中

lea eax,[ecx+edx*2];计算下标值,存入eax中

;一维数组寻址,使用var_10作为基地址,加上下标值eax乘以类型大小4

mov ecx,[esp+eax*4+3Ch+var_10]

push ecx;将ecx作为_printf函数参数压入栈中

push offset aNtwoarrayD;压入字符串"nTwoArray=%d\r\n"

call_printf;调用函数_printf

add esp,44h;平衡栈顶esp

retn

_main endp


代码清单8-12中未能发现二维数组,却出现了奇特的地址下标计算“ecx+edx*2”,此计算中的ecx与edx分别保存二维数组中的两个下标值:i、j。这个计算是从何而来的呢?回顾二维数组的寻址过程如下:

1)使用数组首地址加二维数组下标i乘以一维数组大小,得到一维数组首地址。

2)通过1)获取一维数组首地址后,加下标j乘以类型大小,得到的数据如下:

二维数组type nArry[M][N];使用i、j作为下标寻址

nArray+i*sizeof(type[N])+j*sizeof(type)

=nArray+i*N*sizeof(type)+j*sizeof(type)

=nArray+sizeof(type)*(i*N+j)

通过公式转换后,得到了一个新下标值“i*N+j”,即代码清单8-12中的“ecx+edx*2”,将二维数组的寻址过程转换为了一维数组,节省了一次寻址计算过程,提升了程序执行效率。超过二维的多维数组,最终也以代码清单8-12中的寻址方式出现。如三维数组“int nArray[3][3][3]={{1,2,3},{4,5,6},{7,8,9}};”,使用x、y、z作为三维数组的三个下标值进行寻址,其转换结果如下:


mov eax,[x];取出下标x值存入eax中

mov ecx,[y];取出下标y值存入ecx中

lea edx,[ecx+eax*2];计算下标值

mov ecx,[z];取出下标z值存入ecx中

add eax, edx;经过这条指令后,eax中保存数据为x*3+y

lea edx,[ecx+eax*2];再次执行下标值计算

add eax, edx;此时eax中保存的数据为(x*3+y)*2+z+(x*3+y)

mov eax,[nArray+eax*4];转换得出下标计算值为:(x*3+y)*3+z


三维数组下标值的转换过程是:先把三维数组拆分成3个int[3][3]的二维数组,然后套用二维数组下标值计算公式,得出二维数组的下标值,将其乘以3后得出三维数组下标值。以此类推,即可分析更多维数的数组。

根据下标值的计算可以分析出数组维数,然后根据寻址公式中的类型长度即可得出数组类型。