Указатели на двумерные массивы

Question

Дано задание: разработать функцию 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(&quot;%d&quot;, 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");

}

Answer 1

Мы можем преобразовать матрицу в указать 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. Поправьте меня, если моя логика неправильная!

Answer 2

Код с передачей указателя, место копирования матрицы:

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