Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <conio.h>
- #include <stdio.h>
- struct elem
- {
- int row, column, value;
- elem *prev_i_r, *prev_i_c;
- //prev_i_r - указатель на предыдущий ненулевой элемент в столбце
- //prev_i_c - то же, но в строке
- };
- int n;
- int get_elem (int *e, int *c, elem *col_pos, elem *curr_elem)
- //Получение очредного элемента матрицы, возможно, нулевого.
- //e-порядковый номер считываемого элемента во всей матрице
- //с-то же, но в текущей строке, считая самый правый n-нным.
- {
- int result = 0;
- (*c)--;
- (*e)++;
- if ((*col_pos).prev_i_c == NULL && *c > 0) //Текущая строка нулевая, выведены не все нули
- {
- return 0;
- }
- if ((*col_pos).prev_i_c == NULL && *c == 0) //Текущая строка нулевая, все нули выведены
- {
- *c = n;
- *col_pos = *col_pos -> prev_i_r;
- if ((*col_pos).prev_i_c != NULL) *curr_elem = *col_pos -> prev_i_c;
- return 0;
- //Перходим к следующему заголовочному элементу
- //Если строка ненулевая - новый текущий элемент -
- //последний в строке
- }
- if (*c == (*curr_elem).row && *c > 0 ) //Текущий элемент – C-тый и c>0
- {
- result = curr_elem -> value;
- *curr_elem = *curr_elem -> prev_i_c;
- return result;
- }
- if (*c == (*curr_elem).row && *c == 0 ) //Текущий элемент – C-тый и c=0
- {
- *c = n;
- result = curr_elem -> value;
- *col_pos = *col_pos -> prev_i_r;
- if ((*col_pos).prev_i_c != NULL) *curr_elem = *col_pos -> prev_i_c;
- return result;
- }
- if (*c > (*curr_elem).row) //C-тый элемент - нулевой
- {
- return 0;
- }
- if (*c < (*curr_elem).row) //Выведены все ненулевые элементы
- {
- if (*c == 0) //Вся строка выведена
- {
- *c = n;
- *col_pos = *col_pos -> prev_i_r;
- if ((*col_pos).prev_i_c != NULL) *curr_elem = *col_pos -> prev_i_c;
- return 0;
- }
- return 0;
- }
- }
- void get_list (FILE *in, elem *start)
- //Сборка внутреннего представления матрицы из файла
- //start - заголовочное звено для заголовочных звеньев,
- //основной указатель на всю матрицу
- {
- int temp, r, c;
- elem *h_t, *row_pos, *column_pos, *row_c_p, *column_c_p, *temp_row, *temp_column;
- start -> column = n;
- start -> row = n;
- h_t = start;
- for (r = n; r >= 0; r--) //Создание заголовков столбцов
- {
- h_t -> prev_i_c = new elem;
- h_t = h_t -> prev_i_c;
- h_t -> prev_i_r = NULL;
- h_t -> prev_i_c = NULL;
- h_t -> column = n;
- h_t -> row = r;
- h_t -> value = 0; //Пометка, что пока в этом столбце элементов нет
- }
- h_t = start;
- for (c = n; c >= 0; c--) //Создание заголовков строк
- {
- h_t -> prev_i_r = new elem;
- h_t = h_t -> prev_i_r;
- h_t -> prev_i_r = NULL;
- h_t -> prev_i_c = NULL;
- h_t -> column = c;
- h_t -> row = n;
- h_t -> value = 0; //Пометка, что пока в этой строке элементов нет
- }
- row_pos = start;
- column_pos = start;
- for (c = 0; c < n; c++)
- {
- column_pos = column_pos -> prev_i_r;
- row_pos = start;
- for (r = 0; r < n; r++)
- {
- fscanf(in,"%i",&temp);
- if (temp != 0)
- {
- row_pos = row_pos -> prev_i_c;
- temp_column = column_pos -> prev_i_c;
- column_pos -> prev_i_c = new elem;
- if (column_pos -> value == 0)
- {
- column_c_p = column_pos -> prev_i_c; //Запоминаем указатель на первый созданный в строке элемент
- column_pos -> value = 1; //Помечаем строку как имеющую элементы
- }
- column_pos -> prev_i_c -> column = c; //Добавляем новый элемент в голову
- column_pos -> prev_i_c -> row = r;
- column_pos -> prev_i_c -> value = temp;
- column_pos -> prev_i_c -> prev_i_c = temp_column;
- column_c_p -> prev_i_c = column_pos -> prev_i_c; //И создаем ссылку на него из хвоста
- temp_row = row_pos -> prev_i_r;
- row_pos -> prev_i_r = column_pos -> prev_i_c;
- row_pos -> prev_i_r -> prev_i_r = temp_row;
- if (row_pos -> value == 0 ) //Если создали первый элемент в столбце
- {
- row_pos -> prev_i_r -> prev_i_r = row_pos -> prev_i_r; //ссылаемся из него на него самого
- row_pos -> value = 1; //Помечаем столбец как имеющий элементы
- }
- row_c_p = row_pos -> prev_i_r -> prev_i_r;
- while (row_c_p -> prev_i_r != row_pos -> prev_i_r -> prev_i_r) row_c_p = row_c_p -> prev_i_r;
- row_c_p -> prev_i_r = row_pos -> prev_i_r;
- //Двигаем хвост вверх по столбцу,
- //пока не дойдем до его конца,
- //после этого ссылаемся из хвоста в голову
- }
- }
- }
- }
- void main ()
- {
- FILE *input, *output;
- input = fopen("input.txt","r");
- output = fopen("output.txt","w+");
- fscanf(input,"%i", &n);
- if (n == 1)
- {
- int a, b;
- fscanf(input, "%i %i", &a, &b);
- fprintf(output, "%i", a+b);
- return ;
- //Если матрицы размера 1
- //Нет смысла создавать списки
- //Просто введем 2 числа и выведем их сумму
- }
- elem *A, *B, A_column_pos, A_curr_elem, B_column_pos, B_curr_elem;
- A = new elem;
- A_column_pos = *new elem;
- A_curr_elem = *new elem;
- B = new elem;
- B_column_pos = *new elem;
- B_curr_elem = *new elem;
- get_list(input, A);
- get_list(input, B);
- //Устанавливаем текущие элементы
- //обеих матриц
- //в первый по счету ненулевой элемент
- A_column_pos = *A -> prev_i_r;
- if ((*A).prev_i_r -> prev_i_c != NULL) A_curr_elem = *A -> prev_i_r -> prev_i_c;
- B_column_pos = *B -> prev_i_r;
- if ((*B).prev_i_r -> prev_i_c != NULL) B_curr_elem = *B -> prev_i_r -> prev_i_c;
- int t_A, t_B, counterA, counterB; //t - порядковый номер выводимого элемента матрицы
- counterA = n; //counter - то же для текущей строки
- counterB = n;
- elem *dirty_hack, *begin, *d_h_temp;
- dirty_hack = new elem; //Первый элемент списка для вывода строк
- d_h_temp = new elem;
- dirty_hack -> value = get_elem(&t_A, &counterA, &A_column_pos, &A_curr_elem)
- + get_elem(&t_B, &counterB, &B_column_pos, &B_curr_elem);
- int z;
- for (t_A = 1, t_B = 1 ; t_A < n*n, t_B < n*n; )
- {
- //Строки хранятся задом наперед.
- //Чтобы вывести нормально,
- //создадим новый список,
- //добавляя элементы строки в хвост.
- begin = new elem;
- begin -> value = get_elem(&t_A, &counterA, &A_column_pos, &A_curr_elem)
- + get_elem(&t_B, &counterB, &B_column_pos, &B_curr_elem);
- begin -> prev_i_c = dirty_hack;
- dirty_hack = begin;
- if (t_A % n == 0) //Если достигли конца строки -
- {
- for (z = 0; z < n; z++)
- {
- fprintf(output, "%4i ", dirty_hack -> value);
- d_h_temp = dirty_hack -> prev_i_c;
- delete dirty_hack;
- dirty_hack = d_h_temp;
- //выводим только что сформированный список,
- //удаляя выведенные элементы и перемещая хвост
- //к голове, чтобы не загромождать память
- }
- fprintf(output, "\n");
- dirty_hack = begin;
- }
- }
- fclose(input);
- fclose(output);
- }
Add Comment
Please, Sign In to add comment