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后得出三维数组下标值。以此类推,即可分析更多维数的数组。
根据下标值的计算可以分析出数组维数,然后根据寻址公式中的类型长度即可得出数组类型。