Найти сумму двух сильно разреженных матриц - C (СИ)
Формулировка задачи:
Найти сумму двух сильно разреженных матриц A(m,n) и B(m,n), хранящихся в упакованном виде. Результат получить также в упакованном виде, а вывести — в обычном.
Ну упакую я матрицу в три массива, а вот как сложить их обе в таком виде? Вообще не догоняю. Помогите, товарищи.
Решение задачи: «Найти сумму двух сильно разреженных матриц»
textual
Листинг программы
#include <stdio.h>
#include <glib.h>
typedef struct SPARSE_ARRAY {
gsize rows;
gsize columns;
GHashTable * hash;
} sparse_array_t;
sparse_array_t * sparse_array_new(gsize rows, gsize columns) {
sparse_array_t * sa = g_new(sparse_array_t, 1);
sa->rows = rows;
sa->columns = columns;
sa->hash = g_hash_table_new_full(g_direct_hash, g_direct_equal, NULL, g_free);
return sa;
}
void sparse_array_free(sparse_array_t * sa) {
g_hash_table_destroy(sa->hash);
g_free(sa);
}
void sparse_array_set_at(sparse_array_t * sa, const gsize row, const gsize column, const gdouble value) {
if ( row >= sa->rows )
g_error("row index out of bounds\n");
else if ( column >= sa->columns )
g_error("column index out of bounds\n");
else {
gdouble * pVal = g_new(gdouble, 1);
*pVal = value;
g_hash_table_insert(sa->hash, GSIZE_TO_POINTER(row * sa->columns + column), (gpointer)pVal);
}
}
gdouble * sparse_array_get_at(sparse_array_t * sa, const gsize row, const gsize column) {
if ( row >= sa->rows )
g_error("row index out of bounds\n");
else if ( column >= sa->columns )
g_error("column index out of bounds\n");
else
return (gdouble*)g_hash_table_lookup(sa->hash, GSIZE_TO_POINTER(row * sa->columns + column));
}
/*****************************************************************/
const char * menuItems[] = {
"help", "insert", "retrive", "exit", NULL
};
int main(void) {
int rows, columns, choise;
gboolean finish;
sparse_array_t * sa;
printf("Space separated rows and columns: ");
if ( scanf("%d%d", &rows, &columns) != 2 )
g_error("Wrong input!\n");
sa = sparse_array_new(rows, columns);
finish = FALSE;
while ( ! finish ) {
printf("[0 = help]> ");
if ( scanf("%d", &choise) != 1 )
g_error("Wrong input!\n");
switch(choise) {
case 0: {
int i;
for ( i = 0; menuItems[i]; ++i )
printf("%d - %s\n", i, menuItems[i]);
printf("\n");
break;
}
case 1: {
int row, column;
double val;
printf("Space separated row, column and value: ");
if ( scanf("%d%d%lf", &row, &column, &val) != 3 )
g_error("Wrong input!\n");
sparse_array_set_at(sa, row, column, val);
break;
}
case 2: {
int row, column;
double * valptr;
printf("Space separated row and column: ");
if ( scanf("%d%d", &row, &column) != 2 )
g_error("Wrong input!\n");
valptr = sparse_array_get_at(sa, row, column);
if ( ! valptr )
printf("NULL\n");
else
printf("%f\n", *valptr);
break;
}
case 3: {
finish = TRUE;
break;
}
default:
g_printerr("Unknown option!\n");
}
}
sparse_array_free(sa);
return 0;
}
Объяснение кода листинга программы
- Объяснение кода:
В данном коде представлен алгоритм работы с разреженными матрицами на языке C.
Здесь создается структура
sparse_array_t, которая содержит в себе матрицу. В этой структуре присутствуют следующие поля:rows- количество строк в матрице;columns- количество столбцов в матрице;hash- хэш-таблица, в которой хранятся значения матрицы. Также здесь определены функции:sparse_array_new- создает новую структуруsparse_array_tс заданным количеством строк и столбцов;sparse_array_free- освобождает память, выделенную под структуруsparse_array_t;sparse_array_set_at- устанавливает значение в заданной ячейке матрицы;sparse_array_get_at- возвращает значение из заданной ячейки матрицы. В функцииmainсоздается матрица с заданным количеством строк и столбцов, после чего пользователю предлагается ввести номер строки, столбца и значение для добавления в матрицу или номер строки и столбца для получения значения из матрицы.
- Список действий:
- Ввести количество строк и столбцов матрицы;
- Создать новую структуру
sparse_array_tс заданным количеством строк и столбцов; - Ввести номер строки, столбца и значение для добавления в матрицу или номер строки и столбца для получения значения из матрицы;
- Проверить корректность введенных данных;
- Выполнить действия в зависимости от выбранного пункта меню;
- Освободить память, выделенную под структуру
sparse_array_t.