Как работать с субматрицей в матрице по указателю?

У меня есть matrix размера n. Возьмем пример:

введите описание изображения здесь

Моя рекурсивная функция выполняет обработку элементов, лежащих на границе матрицы. Теперь я хочу назвать это (рекурсивный вызов) на внутренней квадратной матрице:

введите описание изображения здесь

Это прототип моей рекурсивной функции:

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

Я знаю, что 2D-массив представляет собой массив внутри массива. Я знаю, что *(mat+1) + 1) даст адрес памяти, который должен быть базовым адресом моей новой матрицы. Вот что я пробовал:

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

Но это не работает, и я получаю segfault, когда пытаюсь получить к нему доступ с помощью [][] .

Вы не можете разыскивать 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 (ИЛИ 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.

Я почти уверен, что нет умного трюка, чтобы легко передать матрицу 2×2 внутреннего квадрата функции, если только вы не должны копировать элементы из центра вашей матрицы в новую матрицу и затем затем скопировать результат.

Это не ответ на поставленный вопрос, но это ответ на лежащую в основе проблему: управление matrixми и представлениями с matrixми с минимальными усилиями.

Это будет собирать downvotes, но это было так полезно в решении основных проблем, когда задавался тип вопроса, который задает OP, я считаю, что здесь стоит показать этот альтернативный подход. Это не интересно для небольших матриц фиксированного размера, поскольку функции только показывают их преимущества, когда размеры больше или меняются.

Для описания матриц я использую следующие две структуры. Я не буду оставлять поддержку пула памяти (что позволяет управлять набором матриц в виде пула, освобождая их сразу, без необходимости управлять каждой матрицей отдельно) и все, что связано с многопоточной операцией и безопасностью streamов, для простоты.

Код может содержать опечатки; если вы заметили, пожалуйста, оставьте комментарий, и я их исправлю.

 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 .

Матрицы обычно объявляются как локальные переменные, а не как указатели. Вам не нужно забывать освобождать каждую отдельную матрицу после того, как она вам больше не нужна. (Пропущенный механизм пула позволяет избежать этого, так как все матрицы в пуле сразу освобождаются).

Каждая matrix относится только к одной структуре владельца. Структуры владельца записывают количество ссылок (количество матриц, относящихся к данным в этой структуре) и освобождаются, когда счетчик ссылок падает до нуля:

 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; } } 

Всякий раз, когда создается новая matrix, создается соответствующая структура владельца:

 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 в этих случаях.

Интересные и полезные случаи позволяют создавать «представления» в других matrixх. Данные, на которые делается ссылка, являются точно такими же - модификация одной из них сразу же видна в других (-ях); это истинное наложение - нет необходимости в копировании памяти. В отличие от большинства библиотек (таких как GSL, Научная библиотека GNU), эти «представления» являются совершенно обычными matrixми. Вот некоторые примеры:

 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; } 

Используя код, аналогичный приведенному выше, вы можете создавать однострочные или одноколонные представления матрицы, описывающие любую строку, столбец или диагональ. (Диагонали особенно полезны в определенных ситуациях.) Подматрицы могут быть зеркалированы или повернуты и так далее. Вы можете безопасно освободить матрицу, для которой вам нужна только подmatrix или другое представление, поскольку счетчик ссылок на структуру владельца отслеживает, когда данные можно безопасно отбросить.

Матричное умножение и другие подобные сложные операции для больших матриц очень чувствительны к проблемам локализации кэша. Это означает, что вам лучше копировать исходные матричные данные в компактные массивы (с правильными выравниваниями массивов и в элементах в правильном порядке для этого операнда). Накладные расходы, вызванные как строкой, так и столбцом, имеющим отдельный шаг (вместо одного, как это типично), фактически минимальны; в моих собственных тестах, пренебрежимо.

Лучшая особенность этого подхода, однако, заключается в том, что он позволяет писать эффективный код, не беспокоясь о том, что такое «реальная» matrix, что такое «представление» и как фактические базовые данные хранятся в массиве, если вы не заботитесь , Наконец, это достаточно просто для тех, кто полностью понимает базовое управление динамической памятью на языке C.