Как работать с субматрицей в матрице по указателю?
У меня есть матрица размера n. Возьмите пример:
Моя рекурсивная функция выполняет обработку элементов, лежащих на границе матрицы. Теперь я хочу назвать его (рекурсивный вызов) на внутренней квадратной матрице:
Это прототип моей рекурсивной функции:
void rotate(int** mat, size_t n);
Я знаю, что 2D-массив является массивом в массиве. я знаю это *(mat+1) + 1) даст адрес памяти, который должен быть базовым адресом моей новой матрицы. Вот что я попробовал:
rotate((int **)(*(mat+1) + 1), n-2)
Но это не работает, и я получаю segfault, когда я пытаюсь получить к нему доступ с [][],
3 ответа
Вы не можете разыменовать mat+1 и переосмыслить это как указатель на целую матрицу. Вместо этого предоставьте смещения в качестве аргументов вашей функции (я полагаю, n-от-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
// ...
}
Это не ответ на поставленный вопрос, а ответ на основную проблему: управление матрицами и представлениями матриц с минимальными усилиями.
Это будет вызывать отрицательные отзывы, но это было настолько полезно для решения основных проблем, когда бы ни задавался тип вопроса, который задает ОП, я считаю, что здесь стоит показать этот альтернативный подход. Это не интересно для небольших матриц фиксированного размера, поскольку функции показывают свои преимущества только тогда, когда размеры больше или различаются.
Я использую следующие две структуры для описания матриц. Я упущу поддержку пула памяти (которая позволяет управлять набором матриц как пулом, выпуская их все сразу, без необходимости управлять каждой матрицей отдельно) и всем, что связано с многопоточностью и поточной безопасностью, для простоты.
Код может содержать опечатки; если вы заметили, пожалуйста, оставьте комментарий, и я исправлю их.
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 }
матрица m элемент в строке rстолбец c, является m.origin[r * m.rowstride + c * m.colstride]предполагая 0 <= r && r < m.rows а также 0 <= 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, чтобы полностью понять.
Я не уверен в вашем приложении, но мне интересно, поможет ли использование #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 являются указателями на матрицу и матрицу2.
Я почти уверен, что не существует хитрого трюка, чтобы можно было легко передать внутреннюю квадратную матрицу 2x2 в функцию, если только вы не скопировали элементы из центра вашей матрицы в новую матрицу, а затем скопировали результат обратно.