Цитата(hello19 @ 26.2.2012, 13:58  ) | | Нет, матрица обычная 100 000 * 100 000 |
Если размер матрицы фиксирован, то её можно превратить в линейный список: [i][j] => [i*N+j], хотя 100 000 * 100 000 в int уже не влезают... Тогда можно хранить два набора индексов:
| Код |
struct
{
size_t count;
size_t reserved;
double *values;
unsigned int *x;
unsigned int *y;
} spmatrix;
|
| Цитата(hello19 @ 26.2.2012, 13:58 ) | | Что-то не соображу как реализовать поиск элементов... |
Список индексов - отсортированный, поэтому можно воспользоваться бинарным поиском:| Код |
BOOL spmatrixFind( spmatrix *m, unsigned int x, unsigned int y, unsigned int *pindex)
{
BOOL result = FALSE;
unsigned int lower, upper;
int cmp;
if( m->count == 0 )
lower = 0;
else
for( lower = 0, upper = m->count-1; lower <= upper; )
{
unsigned int midpoint = (lower + upper) >> 1;
if( m->x[midpoint] < x )
cmp = -1;
else if( m->x[midpoint] > x )
cmp = 1;
else if( m->y[midpoint] < y )
cmp = -1;
else if( m->y[midpoint] > y )
cmp = 1;
else /* cmp = 0; */
{
result = TRUE;
lower = midpoint;
break;
}
if( cmp > 0 )
lower = midpoint + 1;
else if( midpoint == 0 )
break;
else
upper = midpoint - 1;
}
if( pindex != NULL ) *pindex = lower;
return result;
}
|
Если элемент [x][y] не найден, значит его значение 0.0, иначе m->values[*pindex].
Добавлено @ 14:48
Аналогично пишется spmatrixAdd( m, x, y, value):- делаем spmatrixFind( m, x, y, &index)
- если такой элемент найден, заменяете его значение на value (на этом всё)
- если не найден, то тогда имеем индекс, куда нужно производить вставку (чтобы сохранить отсортированность матричных индексов)
- 1. проверяем, есть ли свободная память в списках (m->count < m->reserved); если нет, то увеличиваем значение для reserved и перезаказываем память на все три списка (m->values, m->x, m->y) (или заказываем память, если reserved был нулевой)
- 2. сдвигаем списки с [index] до [count-1] включительно на одну позицию вправо (освобождаем место в позиции index)
- 3. помещаем значания x, y, value в освободившуюся позицию index
- 4. count увеличиваем на 1
|