多维数组(Multi-dimensional Array)
1. 多维数组的概念
多维数组是指二维及以上的数组。数组是下标(index)和值(value)组成的序对的集合。在数组中，每个有定义的下标都与一个值对应，这个值称作数组元素。
(1)二维数组：”数组元素为一维数组”的一维数组。
(2)三维数组：”数组元素为二维数组”的一维数组。
(3)四维数组：”数组元素为三维数组”的一维数组，如此类推。静态数组和动态数组的区别：
(1)静态数组：必须在定义它时指定其大小和类型，在程序运行过程中其结构不能改变，在程序执行结束时自动撤销。
(2)动态数组：在程序运行过程中才为它分配存储空间。
2. n维数组的逻辑结构
2.1 一维数组的逻辑结构
一维数组中，每一个元素在数组中的位置由下标唯一确定。一维数组中，除第一个元素外，其他元素有且仅有一个直接前驱，第一个元素没有前驱，除最后一个元素外，其他元素有且仅有一个直接后继，最后一个元素没有后继。注：一维数组是指具有相同数据类型的n(n≥0，n为数组长度或数组大小，若n=0就是空数组)个元素的有限序列，因此，一维数组称为向量。
2.2 二维数组的逻辑结构
二维数组(如a[n][m])中，每一个元素(a[i][j](0≤i≤n-1， 0≤j≤m-1))，同时处于第i个行向量和第j个列向量之中。二维数组(如a[n][m])中，每一个元素(a[i][j](0≤i≤n-1， 0≤j≤m-1))，在行的方向和列的方向各有一个直接前驱和一个直接后继，分别是a[i][j-1]，a[i-1][j]和a[i][j+1]，a[i+1][j]。二维数组(如a[n][m])中，每一个元素(a[i][j](0≤i≤n-1， 0≤j≤m-1))，在数组中的位置需由下标的二元组[i][j]唯一确定。二维数组(也称矩阵)，矩阵第0列的元素在行的方向没有前驱，第m-1列的元素在行的方向没有后继，第0行的元素在列的方向没有前驱，第n-1行的元素在列的方向没有后继。注：二维数组称为矩阵，它可以看作是由n个行向量和m个列向量所组成的向量，即二维数组a[n][m]是一个矩阵，总共有n*m个数组元素。因此，二维数组可以看作最简单的非线性结构。
2.3 三维数组的逻辑结构
三维数组(如a[m1][m2][m3])中，每一个元素(a[i][j][k](0≤i≤m1-1， 0≤j≤m2-1， 0≤k≤m3-1))，同时处于3个向量之中。三维数组(如a[m1][m2][m3])中，每一个元素(a[i][j][k](0≤i≤m1-1， 0≤j≤m2-1， 0≤k≤m3-1))，最多有3个直接前驱和3个直接后继。三维数组(如a[m1][m2][m3])中，每一个元素(a[i][j][k](0≤i≤m1-1， 0≤j≤m2-1， 0≤k≤m3-1))，在数组中的位置需由下标的三元组[i][j][k]唯一确定。注：如此类推，在一个n维数组(如a[m1][m2]……[mn])中，总共有m1 * m2 * …… * mn个数组元素。每一个数组元素(a[i1][i2]……[in](0≤i1≤m1-1， 0≤i2≤m2-1， ……，0≤in≤mn-1))，同时处于n个向量之中，其位置由下标的n元组[i1][i2]……[in]唯一确定。
3. n维数组的存储表示
注：多维数组实际上是用一维数组实现的，那么可以利用一维数组的存储方式来表示多维数组。在实现数组的存储时，通常是按各个数组元素的排列顺序，顺次存放在一个连续的存储区域中，这样得到一个所有数组元素的线性序列。
3.1 一维数组的存储表示
注：一维数组a[n]，数组第一个元素的存储起始地址为a，每个数组元素的存储大小为len。数组元素的存储地址的递推公式：
数组元素的存储地址表：
数组下标 index(i)[0][1][2]……[n-1]存储地址 LOC(i)aa+1* lena+2* len……a+(n-1)* len
3.2 二维数组的存储表示
注：按行优先的顺序存储。二维数组数组a[n][m]，数组第一个元素的存储起始地址为a，每个数组元素的存储大小为len。数组元素的存储地址的递推公式：
数组元素的存储地址表：
数组下标 index(i,j)[0][0][0][1][0][2]……[n-1][m-1]存储地址 LOC(i,j)aa+(0* m+1)* lena+(0* m+2)* len……a+((n-1)* m+(m-1))* len
3.3 三维数组的存储表示
注：按行优先的顺序存储。三维数组数组a[m1][m2][m3]，数组第一个元素的存储起始地址为a，每个数组元素的存储大小为len。数组元素的存储地址的递推公式：
数组元素的存储地址表：
数组下标 index(i,j,k)[0][0][0][0][0][1][0][0][2]……[m1-1][m2-1][m3-1]存储地址 LOC(i,j,k)aa+(0* m2* m3+0* m3+1)* lena+(0* m2* m3+0* m3+2)* len……a+((m1-1)* m2* m3+(m2-1)* m3+(m3-1))* len
4. n维数组的实现
相关转换实现文件：Transform.h
#include
#include
#include
using namespace std;
struct Item;
string hex_to_string(Item* item)
{
string str;
stringstream sstr;
sstr< sstr>>str; return str; } int hex_to_decimal(const char* szHex) { int decimal = 0; for (int i=0; szHex[i] != '\0'; i++) { if ((szHex[i] >= '0') && (szHex[i] <= '9')) { decimal = decimal*16 + szHex[i] - '0'; } if ((szHex[i] >= 'a') && (szHex[i] <= 'f')) { decimal = decimal*16 + szHex[i] - 'a' + 10; } if ((szHex[i] >= 'A') && (szHex[i] <= 'F')) { decimal = decimal*16 + szHex[i] - 'A' + 10; } } return decimal; } void decimal_to_hex(string& szHex, int szDecimal) { if(szDecimal == 0) { return; } decimal_to_hex(szHex, szDecimal/16); int m = szDecimal % 16; szHex += char(m + (m< 10 ? '0' : 'A' - 10)); } 4.1 一维数组的实现 静态分配存储空间，文件：OneDimensionalArray.cpp #include "Transform.h" const char dimension = '1'; //使用预编译指令#pragma pack(value)来告诉编译器，使用指定的对齐值来取代缺省的。 //目的是让struct不字节对齐(默认是字节对齐的)。 #pragma pack(1) struct Item { int x; char dimension; }; int main() { const int n = 6; Item OneDimensionalArray[n]; for (int i = 0; i < n; i++) { Item item; item.x = i; item.dimension = dimension; OneDimensionalArray[i] = item; } Item *a = OneDimensionalArray; int len = sizeof(Item); cout << "* 静态分配存储空间，一维数组OneDimensionalArray[" << n << "]。" << endl; cout << "\n* 数组第一个元素的存储起始地址：a = &OneDimensionalArray[0] = OneDimensionalArray = " << a << endl; cout << "\n* 每个数组元素的存储大小：len = sizeof(Item) = " << len << endl; cout << "\n$ 输出数组中所有元素的值及其存放地址==>" << endl; for (int i = 0; i < n; i++) { cout << "item[" << i << "]=" << OneDimensionalArray[i].x << ", " << "LOC(" << i << ") = a+i*len = " << hex_to_decimal(hex_to_string(a).c_str()) + i * len << " = &OneDimensionalArray[" << i << "] = " << &OneDimensionalArray[i] << endl; } system("pause"); return 0; }动态分配存储空间，文件：OneDimensionalArray.cpp #include "Transform.h" const char dimension = '1'; //使用预编译指令#pragma pack(value)来告诉编译器，使用指定的对齐值来取代缺省的。 //目的是让struct不字节对齐(默认是字节对齐的)。 #pragma pack(1) struct Item { int x; char dimension; }; int main() { int n = 0; cout << "$ 请输入一维数组的元素个数，n = "; cin >> n; Item *OneDimensionalArray = new Item[n]; for (int i = 0; i < n; i++) { Item item; item.x = i; item.dimension = dimension; OneDimensionalArray[i] = item; } Item *a = OneDimensionalArray; int len = sizeof(Item); cout << "\n* 动态分配存储空间，一维数组OneDimensionalArray[" << n << "]。" << endl; cout << "\n* 数组第一个元素的存储起始地址：a = &OneDimensionalArray[0] = OneDimensionalArray = " << a << endl; cout << "\n* 每个数组元素的存储大小：len = sizeof(Item) = " << len << endl; cout << "\n$ 输出数组中所有元素的值及其存放地址==>" << endl; for (int i = 0; i < n; i++) { cout << "item[" << i << "]=" << OneDimensionalArray[i].x << ", " << "LOC(" << i << ") = a+i*len = " << hex_to_decimal(hex_to_string(a).c_str()) + i * len << " = &OneDimensionalArray[" << i << "] = " << &OneDimensionalArray[i] << endl; } delete[] OneDimensionalArray; OneDimensionalArray = NULL; system("pause"); return 0; } 4.2 二维数组的实现 静态分配存储空间，文件：TwoDimensionalArray.cpp #include "Transform.h" const char dimension = '2'; //使用预编译指令#pragma pack(value)来告诉编译器，使用指定的对齐值来取代缺省的。 //目的是让struct不字节对齐(默认是字节对齐的)。 #pragma pack(1) struct Item { int x; int y; char d; }; int main() { const int n = 2; const int m = 3; Item TwoDimensionalArray[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { Item item; item.x = i; item.y = j; item.d = dimension; TwoDimensionalArray[i][j] = item; } } Item *a = TwoDimensionalArray[0]; int len = sizeof(Item); cout << "* 静态分配存储空间，二维数组TwoDimensionalArray[" << n << "][" << m << "]。" << endl; cout << "\n* 数组第一个元素的存储起始地址：a = &TwoDimensionalArray[0][0] = TwoDimensionalArray[0] = " << a << endl; cout << "\n* 每个数组元素的存储大小：len = sizeof(Item) = " << len << endl; cout << "\n$ 输出数组中所有元素的值及其存放地址==>" << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cout << "item[" << i << "," << j << "]=(" << TwoDimensionalArray[i][j].x << "," << TwoDimensionalArray[i][j].y << "), " << "LOC(" << i << "," << j << ") = a+(i*m+j)*len = " << hex_to_decimal(hex_to_string(a).c_str()) + (i * m + j) * len << " = &TwoDimensionalArray[" << i << "," << j << "] = " << &TwoDimensionalArray[i][j] << endl; } cout << endl; } system("pause"); return 0; }动态分配存储空间，文件：TwoDimensionalArray.cpp #include "Transform.h" const char dimension = '2'; //使用预编译指令#pragma pack(value)来告诉编译器，使用指定的对齐值来取代缺省的。 //目的是让struct不字节对齐(默认是字节对齐的)。 #pragma pack(1) struct Item { int x; int y; char d; }; int main() { int n = 0; int m = 0; cout << "$ 请输入二维数组行的元素个数，n = "; cin >> n; cout << "$ 请输入二维数组列的元素个数，m = "; cin >> m; Item **TwoDimensionalArray = new Item*[m]; for (int i = 0; i < n; i++) { TwoDimensionalArray[i] = new Item[m]; for (int j = 0; j < m; j++) { Item item; item.x = i; item.y = j; item.d = dimension; TwoDimensionalArray[i][j] = item; } } Item *a = NULL; int len = sizeof(Item); cout << "\n* 动态分配存储空间，二维数组TwoDimensionalArray[" << n << "][" << m << "]。" << endl; cout << "\n* 每个数组元素的存储大小：len = sizeof(Item) = " << len << endl; cout << "\n$ 输出数组中所有元素的值及其存放地址==>" << endl; for (int i = 0; i < n; i++) { a = TwoDimensionalArray[i]; cout << "\n* 数组第" << i << "行第一个元素的存储起始地址：a = &TwoDimensionalArray[" << i << "][0] = TwoDimensionalArray[" << i << "] = " << a << endl; for (int j = 0; j < m; j++) { cout << "item[" << i << "," << j << "]=(" << TwoDimensionalArray[i][j].x << "," << TwoDimensionalArray[i][j].y << "), " << "LOC(" << i << "," << j << ") = a+j*len = " << hex_to_decimal(hex_to_string(a).c_str()) + j * len << " = &TwoDimensionalArray[" << i << "," << j << "] = " << &TwoDimensionalArray[i][j] << endl; } cout << endl; } for (int i = 0; i < n; i++) { delete[] TwoDimensionalArray[i]; } delete[] TwoDimensionalArray; TwoDimensionalArray = NULL; system("pause"); return 0; } 4.3 三维数组的实现 静态分配存储空间，文件：ThreeDimensionalArray.cpp #include "Transform.h" const char dimension = '3'; //使用预编译指令#pragma pack(value)来告诉编译器，使用指定的对齐值来取代缺省的。 //目的是让struct不字节对齐(默认是字节对齐的)。 #pragma pack(1) struct Item { int x; int y; int z; char d; }; int main() { const int m1 = 1; const int m2 = 2; const int m3 = 3; Item ThreeDimensionalArray[m1][m2][m3]; for (int i = 0; i < m1; i++) { for (int j = 0; j < m2; j++) { for (int k = 0; k < m3; k++) { Item item; item.x = i; item.y = j; item.z = k; item.d = dimension; ThreeDimensionalArray[i][j][k] = item; } } } Item *a = ThreeDimensionalArray[0][0]; int len = sizeof(Item); cout << "* 静态分配存储空间，三维数组ThreeDimensionalArray[" << m1 << "][" << m2 << "][" << m3 <<"]" << endl; cout << "\n* 数组第一个元素的存储起始地址：a = &ThreeDimensionalArray[0][0][0] = ThreeDimensionalArray[0][0] = " << a << endl; cout << "\n* 每个数组元素的存储大小：len = sizeof(Item) = " << len << endl; cout << "\n$ 输出数组中所有元素的值及其存放地址==>" << endl; for (int i = 0; i < m1; i++) { for (int j = 0; j < m2; j++) { for (int k = 0; k < m3; k++) { cout << "item[" << i << "," << j << "," << k << "]=(" << ThreeDimensionalArray[i][j][k].x << "," << ThreeDimensionalArray[i][j][k].y << "," << ThreeDimensionalArray[i][j][k].z << "), " << "LOC(" << i << "," << j << "," << k << ") = a+(i*m2*m3+j*m3+k)*len = " << hex_to_decimal(hex_to_string(a).c_str()) + (i * m2 * m3 + j * m3 + k) * len << " = &ThreeDimensionalArray[" << i << "," << j << "," << k << "] = " << &ThreeDimensionalArray[i][j][k] << endl; } cout << endl; } cout << endl; } system("pause"); return 0; }动态分配存储空间，文件：ThreeDimensionalArray.cpp #include "Transform.h" const char dimension = '3'; //使用预编译指令#pragma pack(value)来告诉编译器，使用指定的对齐值来取代缺省的。 //目的是让struct不字节对齐(默认是字节对齐的)。 #pragma pack(1) struct Item { int x; int y; int z; char d; }; int main() { int m1 = 0; int m2 = 0; int m3 = 0; cout << "$ 请输入三维数组m1方向的元素个数，m1 = "; cin >> m1; cout << "$ 请输入三维数组m2方向的元素个数，m2 = "; cin >> m2; cout << "$ 请输入三维数组m3方向的元素个数，m3 = "; cin >> m3; Item ***ThreeDimensionalArray = new Item**[m3]; for (int i = 0; i < m1; i++) { ThreeDimensionalArray[i] = new Item*[m3]; for (int j = 0; j < m2; j++) { ThreeDimensionalArray[i][j] = new Item[m3]; for (int k = 0; k < m3; k++) { Item item; item.x = i; item.y = j; item.z = k; item.d = dimension; ThreeDimensionalArray[i][j][k] = item; } } } Item *a = NULL; int len = sizeof(Item); cout << "\n* 动态分配存储空间，三维数组ThreeDimensionalArray[" << m1 << "][" << m2 << "][" << m3 << "]。" << endl; cout << "\n* 每个数组元素的存储大小：len = sizeof(Item) = " << len << endl; cout << "\n$ 输出数组中所有元素的值及其存放地址==>" << endl; for (int i = 0; i < m1; i++) { for (int j = 0; j < m2; j++) { a = ThreeDimensionalArray[i][j]; cout << "\n* 数组第" << i << "行," << "第" << j << "列第一个元素的存储起始地址：a = &ThreeDimensionalArray[" << i << "][" << j << "][0] = ThreeDimensionalArray[" << i << "][" << j << "] = " << a << endl; for (int k = 0; k < m3; k++) { cout << "item[" << i << "," << j << "," << k << "]=(" << ThreeDimensionalArray[i][j][k].x << "," << ThreeDimensionalArray[i][j][k].y << "," << ThreeDimensionalArray[i][j][k].z << "), " << "LOC(" << i << "," << j << "," << k << ") = a+k*len = " << hex_to_decimal(hex_to_string(a).c_str()) + k * len << " = &ThreeDimensionalArray[" << i << "," << j << "," << k << "] = " << &ThreeDimensionalArray[i][j][k] << endl; } cout << endl; } cout << endl; } for (int i = 0; i < m1; i++) { for (int j = 0; j < m2; j++) { delete[] ThreeDimensionalArray[i][j]; } } for (int i = 0; i < m1; i++) { delete[] ThreeDimensionalArray[i]; } delete[] ThreeDimensionalArray; ThreeDimensionalArray = NULL; system("pause"); return 0; } 参考文献： [1]《数据结构(用面向对象方法与C++语言描述)(第2版)》殷人昆——第四章 [2] 百度搜索关键字：多维数组