Вращая матрицу в ANSI с


У меня есть эта программа С, которая вращается матрица характера. Это простой рерайт этой Java реализации. Как дополнительный \$\тета(Миннесота)\$ предобработки и требуют \$\тета(Миннесота)\$ дополнительное место для запуска произвольных вращений в \$\тета - ((м + н) \мин (М, N)) = \тета(\мах(М, N)\мин(М, N)) = \тета(Миннесота)\$ времени.

rotable_char_matrix.ч

#ifndef ROTABLE_CHAR_MATRIX_H
#define ROTABLE_CHAR_MATRIX_H

#include <stdlib.h>

typedef struct rotation_list_node {
    size_t x;
    size_t y;
    struct rotation_list_node* prev;
    struct rotation_list_node* next;
} rotation_list_node;

typedef struct rotable_char_matrix {
    size_t rows;
    size_t cols;
    size_t number_of_rotation_lists;
    size_t buffer_capacity;
    size_t buffer_size;
    char* data;
    char* buffer;
    rotation_list_node** rotations_list_heads;
    size_t* rotation_list_lengths;
} rotable_char_matrix;

/********************************
* Initializes a rotable matrix. *
********************************/
void rotable_char_matrix_init(rotable_char_matrix* matrix,
                              size_t rows,
                              size_t columns);

/******************************************
* Releases all the resources of a matrix. *
******************************************/
void rotable_char_matrix_clean(rotable_char_matrix* matrix);

/***********************************************
* Reads an individual character from a matrix. *
***********************************************/
char rotable_char_matrix_get(rotable_char_matrix* matrix,
                             size_t x,
                             size_t y);

/*********************************************************
* Writes a character at a particular spot in the matrix. *
*********************************************************/
void rotable_char_matrix_set(rotable_char_matrix* matrix,
                             size_t x,
                             size_t y,
                             char value);

/**************************************************************************
* Rotates the entire matrix 'abs(count)' steps. Positive value of 'count' *
* rotates clockwise, negative value of 'count' rotates counter-clockwise. *
**************************************************************************/
void rotable_char_matrix_rotate(rotable_char_matrix* matrix,
                                int count);

/***********************************************
* Returns the number of columns in the matrix. *
***********************************************/
size_t rotable_char_matrix_columns(rotable_char_matrix* matrix);

/********************************************
* Returns the number of rows in the matrix. *
********************************************/
size_t rotable_char_matrix_rows(rotable_char_matrix* matrix);

#endif /* ROTABLE_CHAR_MATRIX_H */

rotable_char_matrix.с

#include "rotable_char_matrix.h"
#include <stdlib.h>
#define MIN(X,Y) (((X) < (Y)) ? (X) : (Y))

/********************************************************
* Checks that the number of requested rows is not zero. *
********************************************************/
static void check_number_of_rows(size_t rows)
{
    if (rows == 0)
    {
        abort();
    }
}

/***********************************************************
* Checks that the number of requested columns is not zero. *
***********************************************************/
static void check_number_of_cols(size_t cols)
{
    if (cols == 0)
    {
        abort();
    }
}

/*******************************************************************************
* Populate the 'rotation_list_index'th rotation list. The list with index zero *
* is the outermost.                                                            *
*******************************************************************************/
static void populate_rotation_list_at_index(rotable_char_matrix* matrix,
                                            size_t rotation_list_index)
{
    rotation_list_node* previous_node = NULL;
    rotation_list_node* current_node;
    size_t x;
    size_t y;

    for (x = rotation_list_index; x != matrix->cols - rotation_list_index; x++)
    {
        current_node = malloc(sizeof(*current_node));
        current_node->x = x;
        current_node->y = rotation_list_index;

        if (previous_node == NULL)
        {
            matrix->rotations_list_heads[rotation_list_index] = current_node;
        }
        else
        {
            previous_node->next = current_node;
            current_node->prev = previous_node;
        }

        previous_node = current_node;
    }

    for (y = rotation_list_index + 1;
         y != matrix->rows - rotation_list_index - 1;
         y++)
    {
        current_node = malloc(sizeof(*current_node));
        current_node->x = matrix->cols - rotation_list_index - 1;
        current_node->y = y;
        previous_node->next = current_node;
        current_node->prev = previous_node;
        previous_node = current_node;
    }

    for (x = matrix->cols - rotation_list_index - 1;
         x > rotation_list_index;
         x--)
    {
        current_node = malloc(sizeof(*current_node));
        current_node->x = x;
        current_node->y = matrix->rows - rotation_list_index - 1;
        previous_node->next = current_node;
        current_node->prev = previous_node;
        previous_node = current_node;
    }

    /**************************************************************************
    * If in the above loop 'rotation_list_index' is zero, the loop will never *
    * terminate. For this reason, we "unroll" the last iteration out of it.   *
    **************************************************************************/
    current_node = malloc(sizeof(*current_node));
    current_node->x = rotation_list_index;
    current_node->y = matrix->rows - rotation_list_index - 1;
    previous_node->next = current_node;
    current_node->prev = previous_node;
    previous_node = current_node;

    for (y = matrix->rows - rotation_list_index - 2;
         y > rotation_list_index;
         y--)
    {
        current_node = malloc(sizeof(*current_node));
        current_node->x = rotation_list_index;
        current_node->y = y;
        previous_node->next = current_node;
        current_node->prev = previous_node;
        previous_node = current_node;
    }

    previous_node->next = matrix->rotations_list_heads[rotation_list_index];
    matrix->rotations_list_heads[rotation_list_index]->prev = previous_node;
    matrix->rotation_list_lengths[rotation_list_index] =
        2 * (matrix->cols - 2 * rotation_list_index) +
        2 * (matrix->rows - 2 * (rotation_list_index + 1));
}

/**************************************************
* Populates all the rotation lists of the matrix. *
**************************************************/
static void populate_rotation_lists(rotable_char_matrix* matrix)
{
    size_t rotation_list_index;

    for (rotation_list_index = 0;
         rotation_list_index != matrix->number_of_rotation_lists;
         rotation_list_index++)
    {
        populate_rotation_list_at_index(matrix, rotation_list_index);
    }
}

/********************************
* Initializes a rotable matrix. *
********************************/
void rotable_char_matrix_init(rotable_char_matrix* matrix,
                              size_t rows,
                              size_t cols)
{
    if (matrix != NULL)
    {
        check_number_of_rows(rows);
        check_number_of_cols(cols);
        matrix->rows = rows;
        matrix->cols = cols;
        matrix->data = calloc(rows * cols, sizeof(char));
        matrix->buffer_capacity = rows + cols - 2;
        matrix->buffer = malloc(sizeof(char) * (matrix->buffer_capacity));
        matrix->buffer_size = 0;
        matrix->number_of_rotation_lists = MIN(rows / 2, cols / 2);
        matrix->rotation_list_lengths =
        malloc(matrix->number_of_rotation_lists *
               sizeof(*matrix->rotation_list_lengths));

        matrix->rotations_list_heads =
        malloc(matrix->number_of_rotation_lists *
               sizeof(*matrix->rotations_list_heads));

        populate_rotation_lists(matrix);
    }
}

/*************************
* Frees a rotation list. *
*************************/
static void free_single_rotation_list(rotation_list_node* head)
{
    rotation_list_node* current_node;
    rotation_list_node* next_node;
    head->prev->next = NULL;

    for (current_node = head; current_node != NULL; current_node = next_node)
    {
        next_node = current_node->next;
        free(current_node);
    }
}

/********************************************
* Frees all the rotation lists of a matrix. *
********************************************/
static void free_rotation_lists(rotable_char_matrix* matrix)
{
    size_t rotation_list_index;

    for (rotation_list_index = 0;
         rotation_list_index != matrix->number_of_rotation_lists;
         rotation_list_index++)
    {
        free_single_rotation_list(
                            matrix->rotations_list_heads[rotation_list_index]);
    }
}

/******************************************
* Releases all the resources of a matrix. *
******************************************/
void rotable_char_matrix_clean(rotable_char_matrix* matrix)
{
    free_rotation_lists(matrix);
    free(matrix->buffer);
    free(matrix->data);
    free(matrix->rotation_list_lengths);
    free(matrix->rotations_list_heads);
}

/***********************************************
* Reads an individual character from a matrix. *
***********************************************/
char rotable_char_matrix_get(rotable_char_matrix* matrix, size_t x, size_t y)
{
    return matrix->data[matrix->cols * y + x];
}

/*********************************************************
* Writes a character at a particular spot in the matrix. *
*********************************************************/
void rotable_char_matrix_set(rotable_char_matrix* matrix,
                             size_t x,
                             size_t y,
                             char value)
{
    matrix->data[matrix->cols * y + x] = value;
}

/******************************************************************************
* Rotates a 'rotation_list_index'th rotation list in the matrix 'count' steps *
* counter-clockwise.                                                          *
******************************************************************************/
static void rotate_rotation_list_counter_clockwise(rotable_char_matrix* matrix,
                                                   size_t rotation_list_index,
                                                   size_t count)
{
    rotation_list_node* source_node;
    rotation_list_node* target_node;

    source_node = matrix->rotations_list_heads[rotation_list_index];
    target_node = source_node;

    size_t i;

    for (i = 0; i != count; i++)
    {
        matrix->buffer[i] = rotable_char_matrix_get(matrix,
                                                    source_node->x,
                                                    source_node->y);
        source_node = source_node->next;
    }

    for (i = 0;
         i != matrix->rotation_list_lengths[rotation_list_index] - count;
         i++)
    {
        rotable_char_matrix_set(matrix,
                                target_node->x,
                                target_node->y,
                                rotable_char_matrix_get(matrix,
                                                        source_node->x,
                                                        source_node->y));
        target_node = target_node->next;
        source_node = source_node->next;
    }

    for (i = 0; i != count; i++)
    {
        rotable_char_matrix_set(matrix,
                                target_node->x,
                                target_node->y,
                                matrix->buffer[i]);

        target_node = target_node->next;
    }
}

/******************************************************************************
* Rotates a 'rotation_list_index'th rotation list in the matrix 'count' steps *
* clockwise.                                                                  *
******************************************************************************/
static void rotate_rotation_list_clockwise(rotable_char_matrix* matrix,
                                           size_t rotation_list_index,
                                           size_t count)
{
    rotation_list_node* source_node;
    rotation_list_node* target_node;

    source_node = matrix->rotations_list_heads[rotation_list_index];
    target_node = source_node;

    size_t i;

    for (i = 0; i != count; i++)
    {
        matrix->buffer[i] = rotable_char_matrix_get(matrix,
                                                    source_node->x,
                                                    source_node->y);
        source_node = source_node->prev;
    }

    for (i = 0;
         i != matrix->rotation_list_lengths[rotation_list_index] - count;
         i++)
    {
        rotable_char_matrix_set(matrix,
                                target_node->x,
                                target_node->y,
                                rotable_char_matrix_get(matrix,
                                                        source_node->x,
                                                        source_node->y));
        target_node = target_node->prev;
        source_node = source_node->prev;
    }

    for (i = 0; i != count; i++)
    {
        rotable_char_matrix_set(matrix,
                                target_node->x,
                                target_node->y,
                                matrix->buffer[i]);

        target_node = target_node->prev;
    }
}

/*******************************************************************************
* Rotates the 'rotation_list_index'th rotation list of a matrix 'count' steps. *
* If count is positive, rotates clockwise. Otherwise, rotates                  *
* counter-clockwise.                                                           *
*******************************************************************************/
static void rotate_rotation_list(rotable_char_matrix* matrix,
                                 size_t rotation_list_index,
                                 int count)
{
    size_t current_rotation_list_length;
    int count2;

    current_rotation_list_length =
    matrix->rotation_list_lengths[rotation_list_index];

    count %= (int) current_rotation_list_length;

    if (count == 0)
    {
        /* Nothing to do. */
        return;
    }

    if (count < 0)
    {
        /* Rotate counter-clockwise. */
        count = -count;
        count2 = (int)(current_rotation_list_length) - count;

        if (count < count2)
        {
            rotate_rotation_list_counter_clockwise(matrix,
                                                   rotation_list_index,
                                                   count);
        }
        else
        {
            rotate_rotation_list_clockwise(matrix,
                                           rotation_list_index,
                                           count2);
        }
    }
    else
    {
        /* Rotate clockwise. */
        count2 = (int)(current_rotation_list_length) - count;

        if (count < count2)
        {
            rotate_rotation_list_clockwise(matrix,
                                           rotation_list_index,
                                           count);
        }
        else
        {
            rotate_rotation_list_counter_clockwise(matrix,
                                                   rotation_list_index,
                                                   count2);
        }
    }
}

/**************************************************************************
* Rotates the entire matrix 'abs(count)' steps. Positive value of 'count' *
* rotates clockwise, negative value of 'count' rotates counter-clockwise. *
**************************************************************************/
void rotable_char_matrix_rotate(rotable_char_matrix* matrix, int count)
{
    size_t rotation_list_index;

    for (rotation_list_index = 0;
         rotation_list_index != matrix->number_of_rotation_lists;
         rotation_list_index++)
    {
        rotate_rotation_list(matrix, rotation_list_index, count);
    }
}

/***********************************************
* Returns the number of columns in the matrix. *
***********************************************/
size_t rotable_char_matrix_columns(rotable_char_matrix* matrix)
{
    return matrix->cols;
}

/********************************************
* Returns the number of rows in the matrix. *
********************************************/
size_t rotable_char_matrix_rows(rotable_char_matrix* matrix)
{
    return matrix->rows;
}

главная.с

#include "rotable_char_matrix.h"
#include <stdio.h>

#define ROWS 4
#define COLS 5

static void print_matrix(rotable_char_matrix* matrix)
{
    size_t row;
    size_t col;

    for (row = 0; row != rotable_char_matrix_rows(matrix); row++)
    {
        for (col = 0; col != rotable_char_matrix_columns(matrix); col++)
        {
            printf("%c", rotable_char_matrix_get(matrix, col, row));
        }

        puts("");
    }
}

int main(int argc, const char * argv[]) {
    int count;
    int tokens_read;
    rotable_char_matrix matrix;
    rotable_char_matrix_init(&matrix, ROWS, COLS);
    char c = 'a';
    size_t row;
    size_t col;

    for (row = 0; row < ROWS; row++)
    {
        for (col = 0; col < COLS; col++)
        {
            rotable_char_matrix_set(&matrix, col, row, c++);
        }
    }

    for (;;)
    {
        print_matrix(&matrix);
        printf("\n> ");
        tokens_read = scanf("%d", &count);

        if (tokens_read != 1 || feof(stdin) || ferror(stdin))
        {
            break;
        }

        rotable_char_matrix_rotate(&matrix, count);
    }

    rotable_char_matrix_clean(&matrix);
    return 0;
}

Критика запросу

Хотелось бы услышать все, что приходит на ум.



137
7
задан 17 февраля 2018 в 08:02 Источник Поделиться
Комментарии
2 ответа

В целом, у меня очень мало отрицательного, чтобы сказать о коде. Тем не менее, есть некоторые вещи, которые я хотел бы придираться о немного:


  1. Я не уверен, что он по-прежнему целесообразно определить MIN как макрос в наше современное время. Вы, вероятно, знаете обо всех недостатках макросы (нет строгой типизации, склонность к плохому поведению из-за отсутствия скобок и т. д.), и вы не имеете каких-либо существенных недостатков, если оно было определено как функция (за исключением вопроса типа ригидности, которая не применяется в вашем случае, поскольку вы используете только MIN Как только и может определить его для соответствующего типа).

  2. На мой взгляд, check_number_of_rows и check_number_of_columns скорее запутывание исходного кода. Поскольку обе эти функции состоят из простой проверки, и их имена на самом деле не передать то, что проверено, вы на самом деле теряет здесь ясность. Встречая вызовы этих функций в коде неизбежно заставляет вас вернуться и прочитать их определения, потому что название просто говорит о том, что проверка проведена, не то что проверить. Мое предложение было бы assert-как способ, которым вы передаете состояние и вызовы, которые abort если это условие не выполняется. Таким образом, вы аннотация часть функциональности езды (не по ошибке), но сохранить самостоятельного объяснения свойств этих проверок.

  3. Вы можете опустить скобки вокруг аргумента sizeof если это не тип аргумента. Например, sizeof(*current_node) может быть записан как sizeof *current_node. Преимущество раскрывая скобки здесь, чтобы было понятно, когда аргумент является переменной и, когда это имя типа.

  4. Я не знаю, насколько вы заботитесь о таких вещах, но в идеале, вы должны проверить возвращаемое значение функции, которая может провалиться. Это включает в себя mallocи если программа терпит неудачу, это вопрос благодати и правильность ли вы позволите ему спать или не корректно (корректность в том смысле, что не изящно подразумевает, что вы составили определенное граничное условие, например, из-за памяти).

  5. Рассмотрим факторинг "после работы"-код из петли. Например,

    rotation_list_node* previous_node = NULL;
    rotation_list_node* current_node;
    size_t x;
    size_t y;

    for (x = rotation_list_index; x != matrix->cols - rotation_list_index; x++)
    {
    current_node = malloc(sizeof(*current_node));
    current_node->x = x;
    current_node->y = rotation_list_index;

    if (previous_node == NULL)
    {
    matrix->rotations_list_heads[rotation_list_index] = current_node;
    }
    else
    {
    previous_node->next = current_node;
    current_node->prev = previous_node;
    }

    previous_node = current_node;
    }

    (взято из populate_rotation_list_at_index) может быть переписано как

    rotation_list_node* previous_node;
    rotation_list_node* current_node;
    size_t x;
    size_t y;

    previous_node = malloc(sizeof *previous_node);
    previous_node->x = rotation_list_index;
    previous_node->y = rotation_list_index;

    matrix->rotations_list_heads[rotation_list_index] = previous_node;

    for (x = rotation_list_index + 1; x != matrix->cols - rotation_list_index;
    x++) {
    current_node = malloc(sizeof *current_node);
    current_node->x = x;
    current_node->y = rotation_list_index;

    previous_node->next = current_node;
    current_node->prev = previous_node;

    previous_node = current_node;
    }

    что имеет простой цикл for тело в обмен на какие-то дублирование кода (который может быть сокращен create_node()-функция при желании). Получить некоторые, теряют часть. Я лично предпочитаю последний вариант, но, в конечном счете, это всего лишь личное предпочтение.


  6. Вы должны выполнить рефакторинг rotate_rotation_list_clockwise и rotate_rotation_list_counter_clockwise. В настоящее время оба метода имеют 44 строк (включая пустые строки), из которых 37 являются одинаковыми. Это делает мою сухую тревожный звоночек идти дикой природы. Хотя ситуация несколько сложнее, самым кратким образом, чтобы объединить эти методы в один общий реализация будет либо использовать макрос, чтобы определить, является ли вы хотите двигаться по часовой стрелке (т. е. иметь все соответствующие графы формы source_node = source_node->prev;) или против часовой стрелки (т. е. иметь все соответствующие графы формы source_node = source_node->next;) направление. Есть и другие варианты: например, можно передать узлов посредством обратного вызова вместо того, чтобы определить, в каком направлении вращения должен двигаться, или вы могли бы объединить два в один, добавив дополнительный параметр, который указывает направление и просто if на нем.

3
ответ дан 18 февраля 2018 в 12:02 Источник Поделиться

Именования

Хороший именования.

Сокрытие информации

Это мой основной точки обзора.

Определение rotation_list_node не требуется rotable_char_matrix.h.

typedef struct rotation_list_node rotation_list_node;

вполне достаточно.

Полное определение должно существовать в rotable_char_matrix.c чтобы разгрузить пользователя rotable_char_matrix подробности и предотвращения прямого доступа.

Далее, рассмотреть возможность сделать то же самое для rotable_char_matrix. Это подразумевает инициализации возвращает указатель, а не код вызова распределение пространства. Также некоторые получают/набор необходимых функций. Но абстракции данных помогает в долгосрочной перспективе.

Автоматическое форматирование

Ниже и другие подразумевают ручного форматирования и непродуктивно. Принять подходящее для вас авто-форматирование стиля и инструмент.

        matrix->buffer[i] = rotable_char_matrix_get(matrix,
source_node->x,
source_node->y);

и

        matrix->buffer[i] = rotable_char_matrix_get(matrix, 
source_node->x, source_node->y);


Незначительные

С printf("\n> "); tokens_read = scanf("%d", &count);лучше застраховать вывода на печать перед началом сканирования с fflush(stdout);.

2
ответ дан 19 февраля 2018 в 02:02 Источник Поделиться