A-B-C
| |
D---E
A-B-C-D-E
A-D-B-C-E
разреженная матрица на базе мультисписка
Подскажите пожалуйста, как на базе мультисписка реализовать представление двумерной разреженной матрицы? У меня есть подсказка, но не знаю, как ей воспользоваться))):
Цитата:
Каждому значению матрицы соответствует один узел, каждому измерению - одна ссылка/*я так поняла, что для двумерной матрицы потребуется двусвязный список - прим. мое*/, при этом ссылки указывают на следующий элемент в данном измерении/*это как???*/. /*Для значений матрицы, равных нулю,не нужны узлы*/
И потом нужно еще реализовать перемножение таких матриц(((
Цитата:
Каждому значению матрицы соответствует один узел, каждому измерению - одна ссылка
каждый узел участвует в нескольких списках
Цитата:
при этом ссылки указывают на следующий элемент в данном измерени
элементы строк матрицы связаны в один список, а элементы столбцов в другой
в прочем каждый узел может хранить линки относящиеся к каждому из списков
Код:
PS: ну или что-то в этом духе, полагаю
Цитата: Ramon
A-B-C
| |
D---E
A-B-C-D-E
A-D-B-C-E
получается, чтобы проверить что "В" в данном примере стоит в превой строке, а не во второй, нужно как-то анализировать, но как я не представляю - по Вашей идее не получится определить, где кончается одна строка(или столбец) и начинается другая, а без этого премножение не осуществишь(
И как все это примерно в коде будет выглядеть?
Попыталась сделать, вот что получилось:
Код:
//C++ code:
#include <list>
using namespace std;
list<int> transform(int **m,int N,int M){
list<int>l;
int i,j;
for (i=0;i<N;++i)
for (j=0;j<M;++j)
if (m[j]!=0)l.push_back(m[j]);//тут надо использовать свой тип,
//потому как получить доступ внутрь типа list нельзя
//но как организовать этот тип чтобы функция push выполняла автоматическую установку указателей?
return l;
}//transform
#include <list>
using namespace std;
list<int> transform(int **m,int N,int M){
list<int>l;
int i,j;
for (i=0;i<N;++i)
for (j=0;j<M;++j)
if (m[j]!=0)l.push_back(m[j]);//тут надо использовать свой тип,
//потому как получить доступ внутрь типа list нельзя
//но как организовать этот тип чтобы функция push выполняла автоматическую установку указателей?
return l;
}//transform
Узел подобной конструкции должен напоминать нечто вроде.
col и row - идентифицируют элемент матрицы
next_col_entry/next_row_entry узазалели на следующий элемент столбца и строки соответственно.
Код:
struct node
{
size_t value;
size_t col;
size_t row;
struct node* next_col_entry;
struct node* next_row_entry;
};
{
size_t value;
size_t col;
size_t row;
struct node* next_col_entry;
struct node* next_row_entry;
};
col и row - идентифицируют элемент матрицы
next_col_entry/next_row_entry узазалели на следующий элемент столбца и строки соответственно.