Guest User

Untitled

a guest
Jul 15th, 2018
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 8.25 KB | None | 0 0
  1. #include <conio.h>
  2. #include <stdio.h>
  3.  
  4. struct elem
  5. {
  6.     int row, column, value;
  7.     elem *prev_i_r, *prev_i_c; 
  8.     //prev_i_r - указатель на предыдущий ненулевой элемент в столбце
  9.     //prev_i_c - то же, но в строке
  10. };                                                             
  11.  
  12. int n;
  13.  
  14. int  get_elem (int *e, int *c, elem *col_pos, elem *curr_elem)
  15.     //Получение очредного элемента матрицы, возможно, нулевого.
  16.     //e-порядковый номер считываемого элемента во всей матрице
  17.     //с-то же, но в текущей строке, считая самый правый n-нным.
  18. {                                                              
  19.     int result = 0;                                                
  20.     (*c)--;
  21.     (*e)++;
  22.     if ((*col_pos).prev_i_c == NULL && *c > 0)  //Текущая строка нулевая, выведены не все нули
  23.     {
  24.         return 0;
  25.     }
  26.     if ((*col_pos).prev_i_c == NULL && *c == 0) //Текущая строка нулевая, все нули выведены
  27.     {
  28.         *c = n;
  29.         *col_pos = *col_pos -> prev_i_r;                                                   
  30.         if ((*col_pos).prev_i_c != NULL) *curr_elem = *col_pos -> prev_i_c;                
  31.         return 0;
  32.         //Перходим к следующему заголовочному элементу
  33.         //Если строка ненулевая - новый текущий элемент -
  34.         //последний в строке
  35.     }
  36.     if (*c == (*curr_elem).row && *c > 0 )  //Текущий элемент – C-тый и c>0
  37.     {
  38.         result = curr_elem -> value;  
  39.         *curr_elem = *curr_elem -> prev_i_c;
  40.         return result;
  41.     }
  42.     if (*c == (*curr_elem).row && *c == 0 ) //Текущий элемент – C-тый и c=0
  43.     {
  44.         *c = n;  
  45.         result = curr_elem -> value;  
  46.         *col_pos = *col_pos -> prev_i_r;
  47.         if ((*col_pos).prev_i_c != NULL) *curr_elem = *col_pos -> prev_i_c;
  48.         return result;
  49.     }
  50.     if (*c > (*curr_elem).row)  //C-тый элемент - нулевой
  51.     {
  52.         return 0;
  53.     }
  54.     if (*c < (*curr_elem).row)  //Выведены все ненулевые элементы
  55.     {  
  56.         if (*c == 0)    //Вся строка выведена
  57.         {
  58.             *c = n;
  59.             *col_pos = *col_pos -> prev_i_r;
  60.             if ((*col_pos).prev_i_c != NULL) *curr_elem = *col_pos -> prev_i_c;
  61.             return 0;
  62.         }  
  63.         return 0;
  64.     }
  65. }
  66.  
  67. void  get_list (FILE *in, elem *start) 
  68.     //Сборка внутреннего представления матрицы из файла
  69.     //start - заголовочное звено для заголовочных звеньев,
  70.     //основной указатель на всю матрицу
  71. {                                                  
  72.     int temp, r, c;                                
  73.     elem  *h_t, *row_pos, *column_pos, *row_c_p, *column_c_p, *temp_row, *temp_column;
  74.     start -> column = n;
  75.     start -> row = n;  
  76.     h_t = start;
  77.     for (r = n; r >= 0; r--)    //Создание заголовков столбцов   
  78.     {
  79.         h_t -> prev_i_c = new elem;
  80.         h_t =  h_t -> prev_i_c;
  81.         h_t -> prev_i_r = NULL;
  82.         h_t -> prev_i_c = NULL;
  83.         h_t -> column = n;
  84.         h_t -> row = r;
  85.         h_t -> value = 0;   //Пометка, что пока в этом столбце элементов нет 
  86.     }
  87.     h_t = start;
  88.     for (c = n; c >= 0; c--)    //Создание заголовков строк 
  89.     {
  90.         h_t -> prev_i_r = new elem;
  91.         h_t = h_t -> prev_i_r;
  92.         h_t -> prev_i_r = NULL;
  93.         h_t -> prev_i_c = NULL;
  94.         h_t -> column = c;
  95.         h_t -> row = n;
  96.         h_t -> value = 0;   //Пометка, что пока в этой строке элементов нет
  97.     }
  98.     row_pos = start;
  99.     column_pos = start;
  100.     for (c = 0; c < n; c++)                                
  101.     {  
  102.         column_pos = column_pos -> prev_i_r;       
  103.         row_pos = start;               
  104.         for (r = 0; r < n; r++)
  105.         {
  106.             fscanf(in,"%i",&temp);
  107.             if (temp != 0)
  108.             {  
  109.                 row_pos = row_pos -> prev_i_c;
  110.                 temp_column = column_pos -> prev_i_c;
  111.                 column_pos -> prev_i_c = new elem;
  112.                 if (column_pos -> value == 0)      
  113.                 {                                                  
  114.                     column_c_p = column_pos -> prev_i_c; //Запоминаем указатель на первый созданный в строке элемент
  115.                     column_pos -> value = 1;             //Помечаем строку как имеющую элементы
  116.                 }          
  117.                 column_pos -> prev_i_c -> column = c;    //Добавляем новый элемент в голову
  118.                 column_pos -> prev_i_c -> row = r;
  119.                 column_pos -> prev_i_c -> value = temp;
  120.                 column_pos -> prev_i_c -> prev_i_c = temp_column;  
  121.                 column_c_p -> prev_i_c = column_pos -> prev_i_c;    //И создаем ссылку на него из хвоста
  122.                 temp_row = row_pos -> prev_i_r;                    
  123.                 row_pos -> prev_i_r = column_pos -> prev_i_c;          
  124.                 row_pos -> prev_i_r -> prev_i_r = temp_row;
  125.                 if (row_pos -> value == 0 )     //Если создали первый элемент в столбце
  126.                 {                                                  
  127.                     row_pos -> prev_i_r -> prev_i_r = row_pos -> prev_i_r; //ссылаемся из него на него самого
  128.                     row_pos -> value = 1;   //Помечаем столбец как имеющий элементы
  129.                 }
  130.                 row_c_p = row_pos -> prev_i_r -> prev_i_r;         
  131.                 while (row_c_p -> prev_i_r != row_pos -> prev_i_r -> prev_i_r) row_c_p  =  row_c_p -> prev_i_r;
  132.                 row_c_p -> prev_i_r = row_pos -> prev_i_r;     
  133.                 //Двигаем хвост вверх по столбцу,
  134.                 //пока не дойдем до его конца,
  135.                 //после этого ссылаемся из хвоста в голову
  136.             }                                                                                                  
  137.         }      
  138.     }  
  139. }
  140.  
  141. void main ()
  142. {
  143.     FILE *input, *output;
  144.     input = fopen("input.txt","r");
  145.     output = fopen("output.txt","w+");
  146.     fscanf(input,"%i", &n);
  147.     if (n == 1)                                                            
  148.     {                                                                      
  149.         int a, b;                                                          
  150.         fscanf(input, "%i %i", &a, &b);
  151.         fprintf(output, "%i", a+b);
  152.         return ;
  153.         //Если матрицы размера 1
  154.         //Нет смысла создавать списки
  155.         //Просто введем 2 числа и выведем их сумму
  156.     }
  157.     elem *A, *B, A_column_pos, A_curr_elem, B_column_pos,  B_curr_elem;
  158.     A  =  new elem;
  159.     A_column_pos  =  *new elem;
  160.     A_curr_elem  =  *new elem;
  161.     B  =  new elem;
  162.     B_column_pos  =  *new elem;
  163.     B_curr_elem  =  *new elem;
  164.     get_list(input, A);
  165.     get_list(input, B);
  166.     //Устанавливаем текущие элементы
  167.     //обеих матриц
  168.     //в первый по счету ненулевой элемент
  169.     A_column_pos = *A -> prev_i_r;                                                         
  170.     if ((*A).prev_i_r -> prev_i_c != NULL)  A_curr_elem = *A -> prev_i_r -> prev_i_c;      
  171.     B_column_pos = *B -> prev_i_r;                                                         
  172.     if ((*B).prev_i_r -> prev_i_c != NULL)  B_curr_elem = *B -> prev_i_r -> prev_i_c;
  173.     int t_A, t_B, counterA, counterB;   //t - порядковый номер выводимого элемента матрицы
  174.     counterA = n;   //counter - то же для текущей строки
  175.     counterB = n;  
  176.     elem *dirty_hack, *begin, *d_h_temp;                                                   
  177.     dirty_hack = new elem;  //Первый элемент списка для вывода строк
  178.     d_h_temp = new elem;
  179.     dirty_hack -> value  =  get_elem(&t_A, &counterA, &A_column_pos, &A_curr_elem)
  180.         + get_elem(&t_B, &counterB, &B_column_pos, &B_curr_elem);
  181.     int z;
  182.     for  (t_A = 1, t_B = 1 ; t_A < n*n, t_B < n*n; )
  183.     {  
  184.         //Строки хранятся задом наперед.
  185.         //Чтобы вывести нормально,
  186.         //создадим новый список,
  187.         //добавляя элементы строки в хвост.
  188.         begin = new elem;                                                                  
  189.         begin -> value  =  get_elem(&t_A, &counterA, &A_column_pos, &A_curr_elem)          
  190.             + get_elem(&t_B, &counterB, &B_column_pos, &B_curr_elem);          
  191.         begin -> prev_i_c = dirty_hack;                                                    
  192.         dirty_hack = begin;
  193.         if (t_A % n == 0)   //Если достигли конца строки -
  194.         {
  195.             for (z = 0; z < n; z++)                                                        
  196.             {
  197.                 fprintf(output, "%4i ", dirty_hack -> value);                              
  198.                 d_h_temp = dirty_hack -> prev_i_c;                                         
  199.                 delete dirty_hack;                                                         
  200.                 dirty_hack = d_h_temp; 
  201.                 //выводим только что сформированный список,
  202.                 //удаляя выведенные элементы и перемещая хвост
  203.                 //к голове, чтобы не загромождать память
  204.             }
  205.             fprintf(output, "\n");
  206.             dirty_hack = begin;
  207.         }
  208.     }
  209.     fclose(input);
  210.     fclose(output);
  211. }
Add Comment
Please, Sign In to add comment