如何通过指针处理矩阵中的子矩阵?

我有一个大小为n的矩阵。 举个例子:

在此处输入图像描述

我的递归函数对位于矩阵边界的元素进行处理。 现在我想在内部矩阵上调用它(递归调用):

在此处输入图像描述

这是我的递归函数的原型:

void rotate(int** mat, size_t n); 

我知道2D数组是数组中的数组。 我知道*(mat+1) + 1)将给出应该是我的新矩阵的基地址的内存地址。 这是我试过的:

 rotate((int **)(*(mat+1) + 1), n-2) 

但它不起作用,当我尝试使用[][]访问它时,我得到一个段错误。

你不能取消引用mat+1并将其重新解释为指向整个矩阵的指针。 而是将偏移量作为函数的参数提供(我假设n by- n平方矩阵):

 void rotate(int** mat, size_t i, size_t j, size_t n) { // assuming row-wise storage int *row0 = mat[j]; // assumes j < n int *row1 = mat[j + 1]; // assumes j + 1 < n // access row0[i..] and row1[i..] } 

如果您有矩阵的连续存储,则可以执行以下操作:

 rotate(int* mat, size_t i, size_t j, size_t n) { int atIJ = mat[j * n + i]; // assuming row-wise storage // ... } 

我不确定你的应用程序,但我想知道是否使用#define作为矩阵大小会有所帮助….

 #define X_SIZE 4 #define Y_SIZE 4 

甚至

 #define N_SIZE 4 

…因为您可以在函数中使用X_SIZE和Y_SIZE(OR N_SIZE)而无需显式传递它们。

在主要你可能会

  int matrix[X_SIZE * Y_SIZE]; 

要么

 int matrix2[N_SIZE * N_SIZE]; 

然后你可以调用第i行和第j列元素

 *(pmatrix + X_SIZE*j + i) 

要么

 matrix[X_SIZE*j + i] 

要么

 *(pmatrix2 + N_SIZE*j + i) 

要么

 matrix2[N_SIZE*j + i] 

其中pmatrix和pmatrix2是指向矩阵和matrix2的指针。

我很确定没有聪明的技巧能够轻松地将内部正方形2×2矩阵传递给函数,除非您将元素从矩阵的中心复制到新矩阵中,然后将结果复制回来。

这不是对所述问题的答案,但它是对基本问题的回答:用最少的努力管理矩阵和对矩阵的观点。

这将获得downvotes,但它在解决潜在问题时非常有用,无论何时提出OP提出的问题类型,我发现值得在此处展示这种替代方法。 对于小尺寸固定尺寸的矩阵来说,它并不有趣,因为这些特征仅在尺寸较大或变化时才显示出它们的优点。

我使用以下两种结构来描述矩阵。 为简单起见,我将省略内存池支持(允许一个管理一组矩阵作为池,一次释放所有矩阵,而不必单独管理每个矩阵)以及与multithreading操作和线程安全相关的所有内容。

代码可能包含拼写错误; 如果您发现任何问题,请发表评论,我会修复它们。

 typedef int data_t; /* Matrix element data type */ struct owner { long refcount; /* Number of referenced to this data */ size_t size; /* Number of elements in data[] */ data_t data[]; /* C99 flexible array member */ }; typedef struct { int rows; /* Number of rows in this matrix */ int cols; /* Number of columns in this matrix */ long rowstride; long colstride; data_t *origin; /* Pointer to element at row 0, col 0 */ struct owner *owner; /* Owner structure origin points to */ } matrix; #define MATRIX_INIT { 0, 0, 0L, 0L, NULL, NULL } 

r ,列c矩阵m元素是m.origin[r * m.rowstride + c * m.colstride] ,假设0 <= r && r < m.rows0 <= c < m.cols

矩阵通常被声明为局部变量,而不是指针。 您需要记住在不再需要之后释放每个单独的矩阵。 (省略的池机制可以避免这种情况,因为池中的所有矩阵都会立即释放。)

每个矩阵都指的是一个所有者结构。 所有者结构记录引用的数量(引用该结构中数据的矩阵的数量),并在引用计数降至零时释放:

 void matrix_free(matrix *const m) { if (m != NULL) { if (m->owner != NULL && --(m->owner.refcount) < 1L) { m->owner.size = 0; free(m->owner); } m->rows = 0; m->cols = 0; m->rowstride = 0L; m->colstride = 0L; m->origin = NULL; m->owner = NULL; } } 

每当创建新矩阵时,都会创建相应的所有者结构:

 int matrix_new(matrix *const m, const int rows, const int cols) { const size_t size = (size_t)rows * (size_t)cols; struct owner *o; if (m == NULL) return errno = EINVAL; m->rows = 0; m->cols = 0; m->rowstride = 0L; m->colstride = 0L; m->origin = NULL; m->owner = NULL; if (rows < 1 || cols < 1) return errno = EINVAL; o = malloc(sizeof (struct owner) + size * sizeof (data_t)); if (o == NULL) { return errno = ENOMEM; o->refcount = 1L; o->size = size; m->rows = rows; m->cols = cols; m->origin = o->data; m->owner = o; #if DEFAULT_COLUMN_MAJOR > 0 /* Default to column-major element order */ m->rowstride = 1L; m->colstride = (long)rows; #else /* Default to row-major element order */ m->rowstride = (long)cols; m->colstride = 1L; #endif return m; } 

请注意,上面没有将矩阵元素初始化为任何值,因此它们最初包含垃圾。

矩阵转置是一个简单,快速的操作:

 void matrix_transpose(matrix *const m) { if (m->rows > 0 && m->cols > 0) { const int rows = m->rows; const int cols = m->cols; const long rowstride = m->rowstride; const long colstride = m->colstride; m->rows = cols; m->cols = rows; m->rowstride = colstride; m->colstride = rowstride; } } 

同样,您可以旋转和镜像矩阵,也记得在这些情况下修改origin成员。

有趣且有用的案例是能够在其他矩阵中创建“视图”。 引用的数据完全相同 - 修改一个在其他数据中立即可见; 这是真正的别名 - 不需要内存复制。 与大多数库(例如GSL,GNU Scientific Library)不同,这些“视图”本身就是完全普通的矩阵。 这里有些例子:

 int matrix_submatrix_from(matrix *const m, const matrix *const src, const int firstrow, const int firstcol, const int rows, const int cols) { if (m == NULL || m == src) return errno = EINVAL; m->rows = 0; m->cols = 0; m->rowstride = 0L; m->colstride = 0L; m->origin = NULL; m->owner = NULL; if (firstrow + rows > src->rows || firstcol + cols > src->cols) return errno = EINVAL; if (src == NULL || src->owner == NULL) return errno = EINVAL; if (src->owner.refcount < 1L || src->owner.size == 0) return errno = EINVAL; else { ++(src->owner.refcount); m->owner = src->owner; } m->origin = src->origin + src->rowstride * firstrow + src->colstride * firstcol; m->rows = rows; m->cols = cols; m->rowstride = src->rowstride; m->colstride = src->colstride; return 0; } int matrix_transposed_from(matrix *const m, const matrix *const src) { if (m == NULL || m == src) return errno = EINVAL; m->rows = 0; m->cols = 0; m->rowstride = 0L; m->colstride = 0L; m->origin = NULL; m->owner = NULL; if (src == NULL || src->owner == NULL) return errno = EINVAL; if (src->owner.refcount < 1L || src->owner.size == 0) return errno = EINVAL; else { ++(src->owner.refcount); m->owner = src->owner; } m->origin = src->origin; m->rows = src->cols; m->cols = src->rows; m->rowstride = src->colstride; m->colstride = src->rowstride; return 0; } 

使用与上面类似的代码,您可以创建描述任何行,列或对角线的单行或单列矩阵视图。 (对角线在某些情况下特别有用。)子矩阵可以镜像或旋转,等等。 您可以安全地释放矩阵,只需要子矩阵或其他视图,因为所有者结构引用计数会跟踪数据何时可以安全丢弃。

矩阵乘法和大型矩阵的其他类似复杂操作对缓存局部性问题非常敏感。 这意味着您最好将源矩阵数据复制到紧凑数组中(数组正确对齐,并且元素的顺序与该操作数的顺序相同)。 行和列都有一个单独的步幅(而不是通常只有一个)所引起的开销实际上是最小的; 在我自己的测试中,可以忽略不计。

然而,这种方法的最佳特点是它可以让你编写高效的代码,而不必担心什么是“真实”矩阵,什么是“视图”,以及实际底层数据如何存储在数组中, 除非你关心 。 最后,对于掌握C语言基本动态内存管理的人来说,这很简单。