Указатели на двумерные массивы
Дано задание: разработать функцию int is_tridiagonal (int *mat,int n); mat – это квадратная матрица размером nxn. Функция должна вернуть 1, если mat – трехдиагональная матрица, и 0 в противном случае.
Трехдиагональная матрица(везде кроме "трех главных" диагоналей стоят 0)
Выполнил задачу элементарным методом, с помощью цикла перебора элементов i-ых - строк, j - столбцов
Но нужно как-то обойтись без этих i,j и решить задачу с помощью указателей
В общем, стоит преобразовать мои циклы примерно на вот такие, не понимаю как это сделать
int *p; ... for (p = &a[0][0]; p <= &a[NUM_ROWS-1][NUM_COLS-1]; p++)
#include <stdio.h>
#define cols 6
void user_matrix(int matrix[cols][cols]);
void matrix_outp(int matrix[cols][cols]);
int is_tridiagonal(int matrix[cols][cols]);
int main() {
int matrix[cols][cols];
user_matrix(matrix);
matrix_outp(matrix);
printf("%d", is_tridiagonal(matrix));
}
void user_matrix(int matrix[cols][cols]) {
for (int i = 0; i < cols; i++) {
for (int j = 0; j < cols; j++) {
printf("Enter matrix[%d][%d]: ", i + 1, j + 1);
scanf_s("%d", &matrix[i][j]);
}
printf("\n");
}
}
void matrix_outp(int matrix[cols][cols])
{
for (int i = 0; i < cols; i++)
{
for (int j = 0; j < cols; j++)
{
printf("%6d", matrix[i][j]);
}
printf("\n");
}
}
// перебор элементов матрицы и проверка на 0
int is_tridiagonal(int matrix[cols][cols]) {
int schet = 0;
// выше главной и следующей после нее
for (int i = 0; i < cols - 1; i++)
{
for (int j = i + 2; j < cols; j++) {
if (matrix[i][j] != 0)
schet++;
}
}
// ниже главной и следующей после нее
for (int i = 1; i < cols; i++)
{
for (int j = 0; j < i - 1; j++)
{
if (matrix[i][j] != 0)
schet++;
}
}
// 3 главные по центру
for (int i = 0; i < cols; i++) {
for (int j = 0; j < cols; j++) {
if (i == j || i == (j - 1) || i == (j + 1)) {
if (matrix[i][j] == 0) {
schet++;
}
}
}
}
if (schet == 0)
printf("Trexdiagonal");
else
printf("NETrexdiagonal");
}
Ответы (2 шт):
Мы можем преобразовать матрицу в указать int* pointer = &matrix[0][0]; и работать как с одномерным массивом.
Если у нас матрица 5x5, N=5:
|1 1 0 0 0|
|1 1 1 0 0|
|0 1 1 1 0|
|0 0 1 1 1|
|0 0 0 1 1|
То одномерный массив:
|1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1|
Если мы разберём матрицы других размеров, то заметим закономерность:
2xA, 3xB, 3xA, 3xB, 3xA, 3xB, 3xA, 3xB, 2xA, где A - это 1, а B - это 0, и 2xA - это два раза A подряд и т.д.
Можем заметить, что A повторяется 3 раза, кроме начала и конца, так как три диагонали. А также 3 раза B, рассмотрев другие примеры получим -- N-2 раза подряд (по первой и последней строчке).
Таким образом, мы знаем откуда начинать -- с 3 элемента (2 индекс), сколько шагать -- проверить N-2 элемента, что равны 0, и пропустить 3 элемента (в сумме N+1), а также знаем, где остановиться -- это до предпоследнего элемента &matrix[N-1][N-2]!
Edit:
@DmitryK заметил, что я не правильно построил условие, которое верно только для N=5, и то, что я сразу не передаю указатель на матрицу в функцию.
Я изменил свой код. Теперь функция сразу принимает указатель на матрицу, но и не использует больше других указателей. Я проверил для 4,5,6 квадратных матриц, что "3xA" начинаются с индекса size и потом увеличиваются на size+1.
Идея заключается в том, как теперь мы ходим по развернутому массиву, ++i просто ходим на одну ячейку, и если условие выполняется, дополнительно перепрыгиваем три диагонали (3xA) i += 3.
(++i + 1)%(size+1)?:(i += 3) -- в (++i + 1) я инкрементирую i, чтобы перейти на следующую ячейку. Потом я увеличиваю на 1, чтобы индекс стал возможно кратен size+1. Потом идет трюк с ?:, т.е. если номер ячейки, увеличенной на 1, кратен size+1, то остаток от деления будет 0. Ноль в условиях - это ложь, поэтому будет выполняться в тернарном операторе часть после :, а если будет другое число, отличное от нуля, т.е. истина, то будет выполняться часть после ? и до :, но там ничего нет, поэтому там и ничего не произойдет.
В теле цикла мы просто берём элемент и проверяем не ноль ли он.
Да, код не использует указатель в том смысле, в котором Вы хотели. За это я прошу прощения.
Код:
#include <stdio.h>
#include <stdbool.h>
#define N 5
/* Old answer, works only for N = 5
bool is_tridiagonal(int size, int matrix[size][size])
{
for (int* pointer = &matrix[0][2]; pointer < &matrix[size-1][size-2]; pointer += size + 1)
if (pointer[0] || pointer[1] || pointer[2])
return false;
return true;
}
*/
bool is_tridiagonal(int size, int* matrix)
{
for (int i = 2; i < size*size-2; (++i + 1)%(size + 1) ?: (i += 3))
if (matrix[i])
return false;
return true;
}
int main(void)
{
int matrix[N][N] = {
{1, 2, 0, 0, 0},
{3, 4, 5, 0, 0},
{0, 6, 7, 8, 0},
{0, 0, 9, 10, 11},
{0, 0, 0, 12, 13},
};
printf("%d", is_tridiagonal(N, (int*) matrix));
return 0;
}
P.S. Поправьте меня, если моя логика неправильная!
Код с передачей указателя, место копирования матрицы:
bool is_tridiagonal(int size, int* matrix)
{
for (int* pointer = matrix + 2; pointer < (matrix + size*size-3); pointer += size + 1)
{ // вот здесь должен быть цикл до size-2 - иначе при размере матрицы отличным от 5 - будет неправильная работа
// сами же в описании написали - "B повторяется N-2 раза"
if (*pointer != 0 || *(pointer + 1) != 0 || *(pointer + 2) != 0) // вот это работает только для N==5
return false;
}
return true;
}
Кроме того, вы проверяете только что не в диагоналях находятся нули. Но не проверяете, что в диагоналях нули отсутствуют.
И ещё момент, сравнение в условии цикла - нужно посчитать с чем сравнивать, чтобы не было ошибки, т.к. там идет приращение нестандартное pointer += size + 1
А ещё нужна проверка что размер матрицы больше 2