Задание к курсовому проекту №7

Разреженные матрицы

Составить программу на языке Си с функциями для обработки прямоугольных разреженных матриц с элементами целого типа, которая:

  1. Вводит матрицы различного размера с одновременным размещением ненулевых элементов в разреженной матрице в соответствии с заданной схемой;
  2. Печатает введенные матрицы во внутреннем представлении и в обычном виде;
  3. Выполняет необходимые преобразования разреженных матриц (или вычисления над ними) путем обращения к соответствующим функциям;
  4. Печатает результат преобразования во внутреннем представлении и в обычном виде.

Отчет в теоретической части должен содержать сложностную оценку операций изменения (замены нулевого ненулевым и наоборот) и поиска элемента, характерных для реализованного представления, оценку преимуществ этого представления, описание примеров матриц, для которых он будет лучше или хуже обычного предствления. Желательно сравнить свой вариант с остальными.

Входные данные

На первой строке входного файла — числа M и N — размеры матрицы, затем следуют MxN элементов матрицы. Далее возможно (в зависимости от вариантов) указание параметров (чисел, элементов вектора-столбца или вектора-строки).

Выходные данные

Матрица во внутреннем представлении, матрица в обычном виде, матрица во внутреннем представлении после преобразования, матрица в обычном виде после преобразования, результат вычисления функции или предиката (присутствует в некоторых вариантах). Варианты внутреннего представления матрицы

Все матрицы хранятся по строкам, в порядке возрастания индексов ненулевых элементов.

Варианты представления матриц

  1. Цепочка ненулевых элементов в векторе со строчным индексированием.

    Вектор A
    Индекс начала 1-й строки в векторе B; индекс начала 2-й строки; ...; индекс начала M-й строки

    Вектор B
    Номер столбца; значение; индекс следующего ненулевого элемента этой строки (или -1); номер столбца; значение; индекс следующего ненулевого элемента этой строки (или -1); ...

    Индекс равный -1 означает отсутствие ненулевых элементов в строке (или в ее остатке).

  2. Один вектор.

    Ненулевому элементу соответствуют две ячейки: первая содержит номер столбца, вторая содержит значение элемента. -1 в первой ячейке означает конец строки, а вторая ячейка в этом случае содержит номер следующей хранимой строки. Значение -1 в обеих ячейках является признаком конца перечня ненулевых элементов разреженной матрицы.

    -1; номер строки; номер столбца; значение; номер столбца; значение; ...; -1; номер строки; номер столбца; значение; -1; -1.

  3. Три вектора.

    Вектор начал строк A
    Индекс начала 1-й строки в векторах B и C; индекс начала 2-й строки; ...; индекс начала M-й строки.

    Вектор B
    Номер столбца; номер столбца; номер столбца; ...; номер столбца; -1.

    Вектор C
    Значение; значение; значение; ...; значение.

  4. Два вектора.

    Вектор A
    kij; ...; kij; -1

    Вектор B
    Значение; значение; ...; значение.

    где kij = i*n + j.

Варианты преобразований

  1. Определить максимальный по модулю элемент матрицы и умножить на него все элементы строки, в которой он находится. Если таких элементов несколько, обработать каждую строку, содержащую такой элемент.
  2. Определить максимальный по модулю элемент матрицы и умножить на его абсолютное значение все элементы столбца, в котором он находится. Если таких элементов несколько, обработать предпоследний столбец, содержащий такой элемент.
  3. Найти ненулевой элемент матрицы, ближайщий (по модулю разности) к заданному значению. Домножить на него элементы строки и столбца, на пересечении которых он расположен. Если таких элементов несколько, обработать первый из столбца с максимальным индексом.
  4. Умножить разреженную матрицу на вектор-столбец и вычислить количество ненулевых элементов результата.
  5. Умножить вектор-строку на разреженную матрицу и вычислить количество ненулевых элементов результата.
  6. Вычислить сумму двух разреженных матриц, проверить, не является ли полученная матрица симметричной.
  7. Найти строку, содержащую наибольшее количество ненулевых элементов, напечатать ее номер и сумму элементов этой строки. Если таких строк несколько, обработать все.
  8. Вычислить произведение двух разреженных матриц. Проверить не является ли полученная матрица диагональной.
  9. Найти столбец, содержащий наибольшее количество ненулевых элементов, напечатать его номер и произведение элементов этого столбца. Если таких столбцов несколько, обработать предпоследний.
  10. Вычислить матрочлен — многочлен первой степени от разреженной матрицы: a*M + b*E, где E — единичная матрица, a и b — числовые константы.
  11. Транспонировать разреженную матрицу относительно побочной диагонали. Выяснить, является ли полученная матрица кососимметрической.

Примеры

struct Vec
{
  int n; // текущее количество элементов
  int max; // под сколько элементов выделена память
  int *mas; // массив
};

struct Matrix
{
  int n, m;
  struct Vec A, B;
};

void error()
{
  printf("Malloc impossible. I quit.\n");
  exit(1);
}

void vec_init(struct Vec *v)
{
  v->mas = (int *)malloc(sizeof(int));
  if (v->mas == NULL)
    error();
  v->max = 1;
  v->n = 0;
}

void put(int a, struct Vec *v)
{
  if (v->n == v->max) { // расширение массива
    v->mas = (int *)realloc(v->mas, 2*v->max*sizeof(int));
    v->max *= 2;
    if (v->mas == NULL)
      error();
  }
  v->mas[v->n] = a;
  v->n++;
}