二维数组

有很多问题需要使用二维的数组来解决，比如说，图像处理、矩阵运算、机器人定位与导航等。虽然C/C++也提供了多维数组的定义方法，但使用起来多少有些不便。在C语言中，我们可以按照如下的方式定义一个\(3 \times 3\)的二维数组，直接通过双下标我们可以访问二维数组中的元素，比如array[1][1]。

        double array[3][3];

但是在程序运行之前我们就必须知道需要多大的存储空间，在很多时候这是不切实际的。比如一个通用的图像处理程序，在运行之前并不可能知道用户将要塞给它一幅多大的图片。在未知的环境中，机器人也不可能知道用多大的矩阵才能描述整幅地图。

在数组一文中，我们了解到在C语言中可以通过malloc和free来动态的申请和释放内存，C++中有关键字new和delete动态的管理内存。我们通过一个指针来记录动态申请的内存，比如下面的array，指向了申请来的9个double的空间，它足以用来保存\(3 \times 3\)的二维数组。但是我们不能通过array的双下标的形式取访问数组中的元素。

        double *array = (double*)malloc(9 * sizeof(double));
        double *array = new double[9];

针对这样一个广泛需要的基础数据结构，我们将对其进行封装，希望得到一个比较友好的接口。在本文中，主要描述C++形式的二维数组封装。

1. 基础数据和初始化

首先，我们定义一个模板类Array2D，它有三个基本字段，如下面代码片段所示。其中，指针array用于记录二维数组的存储空间，rows和cols分别记录了二维数组的尺寸(行数和列数)。在代码片段的第4行中，我们提供了一个默认的构造函数，为这三个成员变量赋予了初值。

        template <class T>
        class Array2D {
            public:
                Array2D() : array(NULL), rows(0), cols(0) {}
                Array2D(int r, int c);
                Array2D(int r, int c, T const & v);
            private:
                T *array;
                int rows;
                int cols;
        };

        Array2D(int r, int c) : array(NULL), rows(0), cols(0)
        {
            resize(r, c);
        }
        Array2D(int r, int c, T const & v) : array(NULL), rows(0), cols(0)
        {
            resize(r, c);
            int n = r * c;
            for (int i = 0; i < n; i++)
                array[i] = v;
        }

为了方便，我们还额外提供了上面右边所示的两个构造函数。这两个函数有两个相同的参数r和c分别指定的数组的尺寸，其中一个函数还有第三个参数用于指定构建的数组的填充数据。它们都调用resize申请内存，如下面的代码片段，我们首先查看当前二维数组尺寸，如果与新尺寸相同就直接返回。

        void resize(int r, int c) {
            if (r == rows && c == cols)
                return;

接下来，计算新尺寸所需的内存数量，并用临时指针arr指示新申请的内存。如果新尺寸的行数或者列数为0，则不需要耗用内存，只需保持指针arr为空。

            int n = r * c;
            T * arr = NULL;
            if (n > 0)
                arr = new T[n];

如果，原来的数组中保存有数据，我们还需要将原有的数据拷贝到新申请的内存中，并释放原有内存。

            if (NULL != array) {
                int rr = (r < rows) ? r : rows;
                int cc = (c < cols) ? c : cols;
                for (int i = 0; i < rr; i++)
                    for (int j = 0; j < cc; j++)
                        arr[i * cols + j] = array[i * cols + j];
                delete [] array;
            }

最后，更新成员变量。

            array = arr;
            rows = r;
            cols = c;
        }

2. 访问元素

我们希望通过下角标的形式访问二维数组中的元素，可以通过重载操作符'()'来实现，如下所示。该重载操作符有两个参数，r和c，分别是下角标中的行索引和列索引。它返回的是对应元素的引用。

        T & operator () (int r, int c) { return array[r * cols + c]; }

如此，我们就可以类似下面的形式读写二维数组中的元素。

        Array2D<double> array(3,3);
        array(0, 0) = 3.1415926;
        double pi = array(0, 0);

上面的操作符'()'的实现同，通过表达式r * cols + c来获取数组元素。这是一种行存储结构，我们把二维数组按行展开，依次存放在动态申请的内存中。对称的，对于二维数组还有列存储结构。下图分别示意了这样两种存储结构。

这样的实现存在一个问题，就是如果我们的访问超出了申请内存的大小，将产生一些莫名的行为。此时，我们应当申请一块更大的内存，将之改写如下:

        T & operator () (int r, int c) {
            if (r > rows || c > cols) {
                int rr = (r > rows) ? r : rows;
                int cc = (c > cols) ? c : cols;
                resize(rr, cc);
            }
            return array[r * cols + c];
        }

3. 增删改

这里所谓的增删改是以行或列为单位进行的，因为如果只删除一个元素将导致二维数组中间产生一个空洞，这是不实际的。

3.1 插入行或者列

下面的左右两个代码片段分别给出了在指定行或者列索引上插入新行或者列，它们各自有两个输入参数，其中r和c指示了插入的索引，n则说明插入多少行或列。首先，在各自函数的一开始先检查插入的索引不能超出二维数组原有的尺寸。

        bool insert_row(int r, int n) {
            if (r > rows)
                return false;

        bool insert_column(int c, int n) {
            if (c > cols)
                return false;

接着，我们计算插入行或者列后的新尺寸，并申请内存记录在指针arr下。

            int nrows = rows + n;
            int nsize = nrows * cols;
            T * arr = new T[nsize];

            int ncols = cols + n;
            int nsize = rows * ncols;
            T * arr = new T[nsize];

然后，把插入索引之前的数据拷贝到新申请的内存中。这里需要注意插入列的内存索引方式，因为我们采用的行存储方式，所以arr通过arr[i * ncols + j]索引元素，而原数据array通过array[i * cols + j]访问数据。

            for (int i = 0; i < r; i++)
                for (int j = 0; j < cols; j++)
                    arr[i * cols + j] = array[i * cols + j];

            for (int j = 0; j < c; j++)
                for (int i = 0; i < rows; i++)
                    arr[i * ncols + j] = array[i * cols + j];

下面，我们在第一层for循环中留出插入的行和列空间，完成插入操作。并把插入索引之后的数据拷贝到arr下。

            for (int i = (r+n); i < nrows; i++)
                for (int j = 0; j < cols; j++)
                    arr[i * cols + j] = array[(i-n) * cols + j];

            for (int j = (c+n); j < ncols; j++)
                for (int i = 0; i < rows; i++)
                    arr[i * ncols + j] = array[i * cols + j - n];

最后，释放二维数组原先的内存，更新基本成员数据。

            delete [] array;
            array = arr;
            rows = nrows;
            return true;
        }

            delete [] array;
            array = arr;
            cols = ncols;
            return true;
        }

3.2 删除行或列

下面的代码片段给出了删除行或列的实现。同样的它们都有两个输入参数，其中r和c是将要删除的行或列的起始索引，n则是将要删除的行数或列数。在函数的一开始，我们需要检查欲删除的数据不要超出现有的尺寸。

        bool remove_row(int r, int n) {
            if ((r + n - 1) >= rows ||
                0 == n || 0 == rows || 0 == cols)
                return false;

        bool remove_column(int c, int n) {
            if ((c + n - 1) >= cols ||
                0 == n || 0 == rows || 0 == cols)
                return false;

然后，计算删除数据后的二维数组尺寸。并定义一个临时指针，用于指示新申请内存的起始地址。

            int nrows = rows - n;
            T * arr = NULL;

            int ncols = cols - n;
            T * arr = NULL;

如果二维数组仍有剩余的数据，我们需要新申请一块内存来保存剩余数据。

            if (nrows > 0) {
                int nsize = nrows * cols;
                arr = new T[nsize];

                for (int i = 0; i < r; i++)
                for (int j = 0; j < cols; j++)
                    arr[i * cols + j] = array[i * cols + j];

                for (int i = r; i < nrows; i++)
                for (int j = 0; j < cols; j++)
                    arr[i * cols + j] = array[(i + n) * cols + j];
            }

            if (ncols > 0) {
                int nsize = rows * ncols;
                arr = new T[nsize];

                for (int j = 0; j < c; j++)
                for (int i = 0; i < rows; i++)
                    arr[i * ncols + j] = array[i * cols + j];

                for (int j = c; j < ncols; j++)
                for (int i = 0; i < rows; i++)
                    arr[i * ncols + j] = array[i * cols + j + n];
            }

最后，释放内存并更新基本数据。

            delete [] array;
            array = arr;
            rows = nrows;
            return true;
        }

            delete [] array;
            array = arr;
            cols = ncols;
            return true;
        }

3.3 交换行或列

交换行或列的逻辑比较简单，因为不涉及到申请新内存的操作，所以我们在讨论完边界条件后，就直接交换指定的两行数据或者两列数据。

        bool swap_row(int r1, int r2) {
            if (r1 >= rows || r2 >= rows)
                return false;
            if(r1 == r2)
                return true;
            for (int j = 0; j < cols; j++) {
                T tmp = array[r1 * cols + j];
                array[r1 * cols + j] = array[r2 * cols + j];
                array[r2 * cols + j] = tmp;
            }
            return true;
        }

        bool swap_column(int c1, int c2) {
            if (c1 >= cols || c2 >= cols)
                return false;
            if(c1 == c2)
                return true;
            for (int i = 0; i < rows; i++) {
                T tmp = array[i * cols + c1];
                array[i * cols + c1] = array[i * cols + c2];
                array[i * cols + c2] = tmp;
            }
            return true;
        }

4. 完

本文中，我们使用C++模板实现了二维数组，并提供了曾删改的操作。从代码中，我们可以看到增加和删除操作的实现会重新申请内存，因此这种数据结构在需要频繁插入和删除数据的场合效率很低。