LinkedMatrix.cpp

#include <iostream>
#include <fstream>

using namespace std;

/*
 Задан целочисленный двухмерный массив a из n строк и m столбцов. Найти номер первого максимального 
 значения среди отрицательных элементов, расположенных до первого элемента, равного Т. Матрицу рассматривать 
 по строкам. В случае отсутствия отрицательных или равных Т элементов или невозможности поиска вывести 
 соответствующие поясняющие сообщения.
*/

/*
Узел связного списка:
value -- значение
right -- соседний узел (условно справа)
down -- соседний узел (условной снизу)
*/
struct Node
{
    int value;
    Node* right;
    Node* down;
};

/*
Представление матрицы:
M -- количество столбцов
N -- количество строк
Root -- корневой узел, имеющий M - 1 соседей вправо и N - 1 соседей вниз (все соседи тоже имеют соседей)
*/
struct Matrix
{
    int M;
    int N;
    Node* Root;
};

Node* CreateNode();
Node* CreateLinkedList(int len, bool is_horizontal);
void AddRow(Matrix** p);
void AddCol(Matrix** p);
void Delete(Matrix** p);
void DeleteNode(Node* node, bool move_right);
Node* At(Matrix* p, int index);
Node* At(Matrix* p, int x, int y);
Matrix* ReadFile();
void Trace(Matrix* mtx);

// Создает новый узел, который = 0 и ни к чему не привязан
Node* CreateNode() 
{
    Node* p = new Node;
    p->value = 0;
    p->right = NULL;
    p->down = NULL;
    return p;
}

/*
Создает линейно связный список узлов, связанных либо вертикально, либо горизонтально
*/
Node* CreateLinkedList(int len, bool is_horizontal)
{
    Node* start = CreateNode();
    Node* last = start;
    len--;
    while (len > 0)
    {
        if (is_horizontal)
        {
            last->right = CreateNode();
            last = last->right;
        }
        else
        {
            last->down = CreateNode();
            last = last->down;
        }

        len--;
    }

    return start;
}

/*
Создает объект матрицы размером 1 * 1, а затем постепенно 
привязывает нужное количество столбцов и строк
*/
Matrix* Create(int m, int n)
{
    Matrix* mtx = new Matrix;
    mtx->M = 1;
    mtx->N = 1;
    mtx->Root = CreateNode();

    for (int y = 1; y < n; y++)
    {
        AddRow(&mtx);
    }

    for (int x = 1; x < m; x++)
    {
        AddCol(&mtx);
    }

    return mtx;
}

/*
Создает линейно связный список длиной равной количеству столбцов в матрице.
Затем ищет самый левый элемент в самом нижнем ряду и связывает каждый его элемент 
с каждым низлежащим элементом нового ряда. 
Связывание: присвоение ссылки на элемент к node->down
*/
void AddRow(Matrix** p)
{
    Matrix* mtx = *p;
    int width = mtx->M;
    int height = mtx->N;

    Node* list = CreateLinkedList(width, true);

    Node* endRow = mtx->Root;
    while (Node* next = endRow->down) {
        endRow = next;
    }

    Node* next = endRow;
    while (next) {
        endRow->down = list;
        list = list->right;
        next = next->right;
        endRow = next;
    }

    mtx->N++;

    *p = mtx;
}

/*
Аналогично предыдущему методу создает колонку в виде вертикально направленного односвязного списка, который 
затем мнимо подставляется справа от матрицы и каждый элемент самого правого столбца связывается с 
соответсвующим ему элементу нового столбца.
*/
void AddCol(Matrix** p)
{
    Matrix* mtx = *p;
    int width = mtx->M;
    int height = mtx->N;

    Node* list = CreateLinkedList(height, false);

    Node* endCol = mtx->Root;
    while (Node* next = endCol->right) {
        endCol = next;
    }

    Node* next = endCol;
    while (next) {
        endCol->right = list;
        list = list->down;
        next = next->down;
        endCol = next;
    }

    mtx->M++;

    *p = mtx;
}

// Удаляет содержимое матрицы: вызывает рекурсивную функцию вычищения связных списков
void Delete(Matrix** p)
{
    Matrix* mtx = *p;
    DeleteNode(mtx->Root, true);
    delete mtx;
}

// Удаляет элемент связного списка, предварительно вызвав самого себя применительно к соседним элементам.
// move_right -- нужен, чтобы правых соседей могли удалять только вызовы из первой итерации.
void DeleteNode(Node* node, bool move_right)
{
    if (node->right && move_right)
        DeleteNode(node->right, move_right);
    if (node->down) 
        DeleteNode(node->down, false);
    
    delete node;
}

/*
Доступ к узлам матрицы по индексу (M * y) + x
x - i-й элемент с нуля
y - j-й элемент с нуля
*/
Node* At(Matrix* mtx, int index) 
{
    int x = index % mtx->M;
    int y = (index - x) / mtx->N;
    return At(mtx, x, y);
}

/*
Достает элемент матрицы по x/y.
Сначала промативыет список на x - 1 раз вправо, затем на y - 1 раз вниз
x - i-й элемент с нуля
y - j-й элемент с нуля
*/
Node* At(Matrix* mtx, int x, int y)
{
    if (x < mtx->M && y < mtx->N) {
        Node* cur = mtx->Root;
        while (x-- > 0) cur = cur->right;
        while (y-- > 0) cur = cur->down;
        return cur;
    }
    return NULL;
}


/*
Вытаскивает числа из файла:
Сначала читаются первые два числа -- создается объект матрицы шириной и длиной в соответствии с первыми двумя числами в файле.
Затем для каждого последующиего числа вычисляется номер элемента в матрице, по кторому и происходит присвоение к нужной позиции.
*/
Matrix* ReadFile()
{
    fstream file("mat.txt", ios_base::in);

    Matrix* mtx = NULL;
    int m = 0;
    int n = 0;
    int i = 0;
    int a = 0;

    while (file >> a)
    {
        if (i == 0) m = a;
        if (i == 1) n = a;

        if (i == 2) {
            mtx = Create(m, n);
        }

        if (i > 1) {
            int index = i - 2;
            Node* item = At(mtx, index);
            item->value = a;
        }

        i++;
    }

    return mtx;
}


/*
Выводит содержимое матрицы на экран.

if(a >= 0) cout << " ";
if(a < 10) cout << " ";   ---- это все сделано, чтобы числа с разным количеством разрядов и наличием минуса смотрелись в ровной сетке а не в кучу
if(a < 100) cout << " ";
*/
void Trace(Matrix* mtx)
{
    for (int y = 0; y < mtx->N; y++)
    {
        for (int x = 0; x < mtx->M; x++)
        {
            Node* node = At(mtx, x, y);
            int a = node ? node->value : 0;

            if(a >= 0) cout << " ";
            if(a < 10) cout << " ";
            if(a < 100) cout << " ";

            cout << " " << a;
        }
        cout << endl << endl;
    }
}


int main()
{
    setlocale(LC_ALL, "Russian");

    Matrix* mtx = NULL;
    bool exit = false;

    while (!exit) 
    {
        cout << endl << "-----------------------------------------------------" << endl;
        cout << "Введите команду:" << endl;
        cout << "1. Загрузить матрицу" << endl;
        cout << "2. Изменить элемент" << endl;
        cout << "3. Изменить размер матрицы" << endl;
        cout << "4. По заданию" << endl;
        cout << "5. Очистить память" << endl;
        cout << "6. Выход" << endl;
        cout << "-----------------------------------------------------" << endl << endl;

        int command = 0;
        cin >> command;

        switch (command)
        {
        case 1:
			// Читает файл, присваивает матрицу к mtx, выводит на экран содержимое
            cout << "Чтение из файла:" << endl;
            mtx = ReadFile();
            Trace(mtx);
            break;
        case 2:
			// Проверяет, что матрица загружена
            if (mtx)
            {
                int m = 0;
                int n = 0;
                cout << endl << "M = ";
                cin >> m;
                cout << endl << "N = ";
                cin >> n;

				// Достает элемент матрицы, ждет ввода пользователя, присваивает введенное число в значение элемента
                if (m >= 0 && n >= 0 && m < mtx->M && n < mtx->N)
                {
                    Node* node = At(mtx, m, n);
                    cout << node->value << " = ";
                    cin >> node->value;
                    cout << endl;

                    Trace(mtx);
                }
                else
                {
                    cout << "Нет такого элемента" << endl;
                }
            }
            else
            {
                cout << "Матрица не загружена из файла" << endl;
            }
            break;
        case 3:
            if (mtx)
            {
                int m = 0;
                int n = 0;
                cout << endl << "M = ";
                cin >> m;
                cout << endl << "N = ";
                cin >> n;

                if (m >= 1 && n >= 1)
                {
                    Matrix* new_mtx = Create(m, n);

                    for (int x = 0; x < new_mtx->M && x < mtx->M; x++) 
                    {
                        for (int y = 0; y < new_mtx->N && y < mtx->N; y++)
                        {
                            At(new_mtx, x, y)->value = At(mtx, x, y)->value;
                        }
                    }

                    Delete(&mtx);
                    mtx = new_mtx;

                    Trace(mtx);
                }
                else
                {
                    cout << "Введите валидные величины" << endl;
                }
            }
            else
            {
                cout << "Матрица не загружена из файла" << endl;
            }
            break;
        case 4:
        {
            if (mtx)
            {
                int T = 0;
                cout << "Введите T:" << endl;
                cin >> T;
                //
                int len = mtx->M * mtx->N;
                int negMax = INT32_MIN; // Если ничего не найдено, то здесь остается это значение (самое минимульно возможное значение int32)

                for (int i = 0; i < len; i++) {
                    Node* item = At(mtx, i); // Достается элемент по индексу

                    if (item->value < 0)
                    {
                        if (item->value > negMax)negMax = item->value;
                    }

                    if (item->value == T) break;
                }

                if (negMax == INT32_MIN)
                {
                    cout << "Не удалось найти максимальное среди отрицательных" << endl;
                }
                else
                {
                    cout << "Максимальное среди отрицательных: " << negMax << endl;
                }
            }
            else
            {
                cout << "Матрица не загружена из файла" << endl;
            }
        }
        break;
        case 5:
            //
            if (mtx) 
            {
                Delete(&mtx);
                mtx = NULL;
            }
            else 
            {
                cout << "Матрица не загружена из файла" << endl;
            }
            //
            break;
        case 6:
            exit = true;
            break;
        default:
            break;
        }
    }

    cout << "Press any key to exit..." << endl;
    system("pause");
    return 0;
}