双指针算术

Question

我有一个二维矩阵

matrix[m][n];

我知道矩阵是一个类型为int**的双指针。我想获得一个双指针指向原矩阵的子矩阵。例如，我想让子矩阵从单元格(1,1)开始。我如何从原始矩阵[m][n]中得到这样一个双指针?

Answer 1

我知道矩阵是int**类型的双指针。

不，你不需要。数组不是指针。如果声明为int matrix[m][n];，则表达式 matrix的类型为int [m][n];除非matrix是sizeof或一元&操作符的操作数，否则它的类型将被转换为int (*)[n](指向n的指针- int的元素数组)。

问题是你不能仅仅通过声明正确类型的指针来创建任意的子矩阵;C和c++没有提供一种简单的方法来"切片"数组。您当然可以创建一个类型为int (*)[n-1]的指针，并将&matrix[1][1]的值赋给它(通过适当的强制转换)，但它不会做您想要的。

编辑

现在我面前有一个真正的键盘，我可以扩展一下。

让我们想象一个3x3矩阵声明如下:

int m[3][3] = {{0,1,2},{3,4,5},{6,7,8}};

我们通常把这样的矩阵看作

+---+---+---+
| 0 | 1 | 2 |
+---+---+---+
| 3 | 4 | 5 |
+---+---+---+
| 6 | 7 | 8 |
+---+---+---+

在C和c++中，二维数组按照row-major顺序排列 ^1,2 ，因此上述矩阵将在内存中表示为

   +---+
m: | 0 | m[0][0]
   +---+
   | 1 | m[0][1]
   +---+
   | 2 | m[0][2]
   +---+
   | 3 | m[1][0]
   +---+ 
   | 4 | m[1][1]
   +---+
   | 5 | m[1][2]
   +---+
   | 6 | m[2][0]
   +---+ 
   | 7 | m[2][1]
   +---+
   | 8 | m[2][2]
   +---+

假设你想要从m[1][1]开始的2x2子矩阵:

+---+---+---+
| 0 | 1 | 2 |
+---+---+---+ 
| 3 | +---+---+
+---+ | 4 | 5 |
| 6 | +---+---+
+---+ | 7 | 8 |
      +---+---+

对应以下数组元素:

   +---+
m: | 0 | m[0][0]
   +---+
   | 1 | m[0][1]
   +---+
   | 2 | m[0][2]
   +---+
   | 3 | m[1][0]
   +---+
     +---+ 
     | 4 | m[1][1]
     +---+
     | 5 | m[1][2]
     +---+
   +---+
   | 6 | m[2][0]
   +---+
     +---+ 
     | 7 | m[2][1]
     +---+
     | 8 | m[2][2]
     +---+

这不是m中的连续子数组，所以只是声明一个指针并将其设置为&m[1][1]不会达到您真正想要的效果。您需要创建一个单独的矩阵对象，并复制您想要的元素到它:

int subm[2][2] = {{m[1][1], m[1][2]}, {m[2][1], m[2][2]}};

你可以写一个函数来抓取矩阵的2x2"切片"，像这样:

void slice2x2( int (*mat)[3], int (*submat)[2], size_t startx, size_t starty )
{
  for ( size_t i = 0; i < 2; i++ )
    for ( size_t j = 0; j < 2; j++ )
      submat[i][j] = mat[startx + i][starty + j];
}
int main( void )
{
  int matrix[3][3] = {{0,1,2},{3,4,5},{6,7,8}};
  int submat[2][2];
  slice2x2( matrix, submat, 1, 1 );
  // do something with submat
}

---

<子>

1. C 2011标准预出版草案，第6.2.5.1节，第3段。
2. c++ 2014标准发布前草案，& section;8.3.4， ¶9

Answer 2

定义为固定大小的二维数组的矩阵:

int matrix [m][n];

存储为m个连续的n个元素块。因此，从技术上讲，您可以将其想象为内存中m*n个元素的平面序列。您可以使用指针算术来查找行开头，或查找特定元素。但是你不能这样定位子矩阵

"double"指针:

int **pmatrix;

遵循不同的逻辑:它是指向另一个指针的指针，并作为一个由m个指针组成的数组，这些指针指向第n个连续元素的行。所以元素不一定是连续的。可以使用指针算术和间接方法来定位行或特定项的起始位置。但是这不能处理子矩阵

matrix和pmatrix都可以用于1D或2D索引，但是编译器生成不同的代码来寻址元素。

要获得子矩阵，你必须使用垂直和水平偏移进行迭代以找到正确的元素，但如果你不将正确的元素复制到目标大小的新矩阵中，你无法想象以某种方式传递指向子矩阵的指针。